Autoreducibility of NP-complete sets

DOI10.4230/LIPICS.STACS.2016.42MaRDI QIDQ4601894zbMATH OpenFDO

Authors John M. Hitchcock, Hadi Shafei

Publication date 24 January 2018

Full work available at URL https://arxiv.org/abs/1601.05494

zbMATH Keywords

autoreducibilitycomputational complexitygenericityNP-completeness

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Autoreducibility of NP-complete sets under strong hypotheses
• Probabilistic autoreductions
• Autoreducibility, mitoticity, and immunity
• Separating Complexity Classes Using Autoreducibility
• Mathematical Foundations of Computer Science 2005

Cited in

(11)

• Autoreducibility of NP-complete sets under strong hypotheses
• On the reducibility of sets inside NP to sets with low information content
• Nonuniform reductions and NP-completeness
• Probabilistic autoreductions
• scientific article; zbMATH DE number 6691435 (Why is no real title available?)
• Automatic Evaluation of Reductions between NP-Complete Problems
• Nonuniform reductions and NP-completeness
• scientific article; zbMATH DE number 4126690 (Why is no real title available?)
• Structural properties of nonautoreducible sets
• Mathematical Foundations of Computer Science 2005
• On the autoreducibility of functions

This page was built for publication: Autoreducibility of NP-complete sets

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