On the theory of the PTIME degrees of the recursive sets

摘要

There 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.