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)

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)