scientific article; zbMATH DE number 4037840

MaRDI QIDQ3778006zbMATH OpenFDO

Authors Klaus Ambos-Spies

Publication date 1987

zbMATH Keywords

minimal pairpolynomial time computablepolynomial time reducibility

Mathematics Subject Classification ID

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

Recommendations

• Minimal pairs and complete problems
• scientific article; zbMATH DE number 18526
• scientific article; zbMATH DE number 700630
• Minimal pairs for P
• On Splitting of a Recursive Set with Polynomial Time Minimal Pairs

Cited in

(26)

• On the relative complexity of hard problems for complexity classes without complete problems
• Minimal m-powers
• Minimal pairs and complete problems
• Undecidability results for low complexity time classes
• Uniformly hard languages.
• Minimization problems for parity OBDDs
• Weak completeness notions for exponential time
• Reductions between disjoint NP-pairs
• Efficiently computing minimal sets of critical pairs
• A characterization of the leaf language classes
• Many-one reductions and the category of multivalued functions
• Constructing minimal pairs of degrees
• scientific article; zbMATH DE number 5125120 (Why is no real title available?)
• scientific article; zbMATH DE number 3930984 (Why is no real title available?)
• On Splitting of a Recursive Set with Polynomial Time Minimal Pairs
• scientific article; zbMATH DE number 18526 (Why is no real title available?)
• scientific article; zbMATH DE number 151766 (Why is no real title available?)
• Exact Pairs for Abstract Bounded Reducibilities
• On the problem of the critical bound
• scientific article; zbMATH DE number 700630 (Why is no real title available?)
• scientific article; zbMATH DE number 1086677 (Why is no real title available?)
• scientific article; zbMATH DE number 7561759 (Why is no real title available?)
• The theory of the polynomial many-one degrees of recursive sets is undecidable
• Differences between resource bounded degree structures
• Computably enumerable equivalence relations via primitive recursive reductions
• Minimal pairs for P

This page was built for publication:

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