Automorphisms in the PTIME-Turing degrees of recursive sets

DOI10.1016/S0168-0072(95)00065-8MaRDI QIDQ676317zbMATH OpenFDO

Authors Christine Ann Haught, Theodore A. Slaman

Publication date 12 June 1997

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0168-0072(95)00065-8

zbMATH Keywords

automorphismsforcingoraclepolynomial Turing degreesrecursive sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Applications of computability and recursion theory (03D80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

If \(A\) and \(B\) are sets then \(A\leq_T^p B\) if there is a polynomial time algorithm, with access to oracle \(B\), that can decide \(A\). Take the set of all recursive sets. If \(A\leq_T^p B\) and \(B\leq_T^p A\) then we will say \(A\) and \(B\) are equivalent. Let \({\mathbf R}\) be the resulting set of degrees, ordered by \(\leq_T^p\). The question arises as to whether this structure has any non-trivial automorphisms. This paper shows that this is a hard question. In this paper, the authors exhibit two oracles. Relative to one of them, there are no automorphisms. Relative to the other one, there are. Hence techniques that relativize will not suffice to answer the question. The construction of the oracles uses forcing.

Recommendations

• scientific article; zbMATH DE number 3869313
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• On relativized nondeterministic polynomial-time bounded computations
• Strong polynomial-time reducibility

Cites work

• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets
• On the Structure of Polynomial Time Reducibility
• On the theory of the PTIME degrees of the recursive sets

Cited in

(5)

• Permutations of the integers induce only the trivial automorphism of the Turing degrees
• Automorphisms of the truth-table degrees are fixed on a cone
• scientific article; zbMATH DE number 64152 (Why is no real title available?)
• Permutations of the integers induce only the trivial automorphism of the Turing degrees
• On the theory of the PTIME degrees of the recursive sets

This page was built for publication: Automorphisms in the PTIME-Turing degrees of recursive sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q676317)