An Inhomogeneity in the Structure of Karp Degrees

DOI10.1137/0215067zbMATH Open0618.03018OpenAlexW72252357MaRDI QIDQ3754607FDOQ3754607

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

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

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)

Cited In (5)

• On Splitting of a Recursive Set with Polynomial Time Minimal Pairs
• Minimal pairs and complete problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• The theory of the polynomial many-one degrees of recursive sets is undecidable

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)