Title :
On the theory of the PTIME degrees of the recursive sets
Author :
Shinoda, Juichi ; Slaman, Theodore A.
Author_Institution :
Nagoya Univ., Japan
Abstract :
An interpretation is given of first-order arithmetic in the theory of the PTIME degrees of the recursive sets, ordered under PTIME Turing reducibility (<REC, ⩽p>). This characterizes the Turing degree of the first-order theory of <REC, ⩽ p>. In particular, it is not decidable
Keywords :
Turing machines; PTIME degrees; Turing reducibility; first-order arithmetic; recursive sets; Arithmetic; Code standards; Computational modeling; Polynomials; Time factors;
Conference_Titel :
Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual
Conference_Location :
Washington, DC
Print_ISBN :
0-8186-0866-8
DOI :
10.1109/SCT.1988.5285
