An Inhomogeneity in the Structure of Karp Degrees

DOI10.1137/0215067MaRDI QIDQ3754607zbMATH OpenOpenAlexFDO

Authors Klaus Ambos-Spies

Publication date 1986

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0215067

zbMATH Keywords

polynomial degreesrecursive setNP-setspolynomial time reducibilitiesKarp degreep-splitting

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• On Splitting of a Recursive Set with Polynomial Time Minimal Pairs
• scientific article; zbMATH DE number 700630
• Splittings of 0' into the Recursively Enumerable Degrees
• Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets
• The universal splitting property. II

Cited in

(5)

• scientific article; zbMATH DE number 205856 (Why is no real title available?)
• Minimal pairs and complete problems
• The theory of the polynomial many-one degrees of recursive sets is undecidable
• On Splitting of a Recursive Set with Polynomial Time Minimal Pairs
• scientific article; zbMATH DE number 4137760 (Why is no real title available?)

This page was built for publication: An Inhomogeneity in the Structure of Karp Degrees

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