Autoreducibility of NP-complete sets under strong hypotheses

DOI10.1007/S00037-017-0157-ZMaRDI QIDQ1745961zbMATH OpenOpenAlexFDO

Authors John M. Hitchcock, Hadi Shafei

Publication date 18 April 2018

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-017-0157-z

zbMATH Keywords

NP-completenessgenericityautoreducibility

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Autoreducibility of NP-complete sets
• Autoreducibility, mitoticity, and immunity
• Probabilistic autoreductions
• Separating Complexity Classes Using Autoreducibility
• Autoreducibility of complete sets for log-space and polynomial-time reductions

Cites work

• scientific article; zbMATH DE number 6691435 (Why is no real title available?)
• scientific article; zbMATH DE number 3869312 (Why is no real title available?)
• scientific article; zbMATH DE number 3343692 (Why is no real title available?)
• A Post's program for complexity theory.
• A comparison of polynomial time reducibilities
• Autoreducibility, mitoticity, and immunity
• Bi-immunity separates strong NP-completeness notions
• Comparing reductions to NP-complete sets
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Diagonalizations over polynomial time computable sets
• Hardness hypotheses, derandomization, and circuit complexity
• Non-uniform reductions
• On being incoherent without being very hard
• Separating Complexity Classes Using Autoreducibility
• Separating NP-completeness notions under strong hypotheses

Cited in

(10)

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

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

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