On the theory of the PTIME degrees of the recursive sets

Shinoda, Juichi
Slaman, Theodore A.

Open link

Publication date

December 1990

DOI

10.1016/0022-0000(90)90024-F

Publisher

Published by Elsevier Inc.

Abstract

AbstractThere is an interpretation of first-order arithmetic in the theory of the PTIME degrees of the recursive sets. There is an interpretation of second-order arithmetic in the first-order theory of the PTIME degrees. These results characterize the Turing degrees of the first order theories of these structures

Extracted data

We use cookies to provide a better user experience.

Data Protection

On the theory of the PTIME degrees of the recursive sets

Abstract

Extracted data

On the theory of the PTIME degrees of the recursive sets

Abstract

Extracted data

Related items

Related items