Computable real function F such that F is not polynomial time computable on [0,1]

Autor:	Yakhontov, Sergey V.
Rok vydání:	2014
Předmět:	Computer Science - Computational Complexity
Druh dokumentu:	Working Paper
Popis:	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)) Comment: 5 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1404.7053 Zobrazit plný text záznamu View this record from Arxiv