Computable real function F such that F is not polynomial time computable on [0,1]
arXiv:1404.7053
Abstract
A computable real function F on [0,1] is constructed such that there exists an exponential time algorithm for the evaluation of the function on [0,1] on Turing machine but there does not exist any polynomial time algorithm for the evaluation of the function on [0,1] on Turing machine (moreover, it holds for any rational point on (0,1))
5 pages