DocumentCode
1842748
Title
On the theory of the PTIME degrees of the recursive sets
Author
Shinoda, Juichi ; Slaman, Theodore A.
Author_Institution
Nagoya Univ., Japan
fYear
1988
fDate
14-17 Jun 1988
Firstpage
252
Lastpage
257
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual
Conference_Location
Washington, DC
Print_ISBN
0-8186-0866-8
Type
conf
DOI
10.1109/SCT.1988.5285
Filename
5285
Link To Document