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

computational complexityNP-completenessgenericityautoreducibility

Mathematics Subject Classification ID

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

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)

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

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)