Autoreducibility of NP-complete sets under strong hypotheses

DOI10.1007/s00037-017-0157-zzbMath1390.68321OpenAlexW2739273244MaRDI QIDQ1745961

Hadi Shafei, John M. Hitchcock

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)

Related Items (1)

Nonuniform reductions and NP-completeness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Comparing reductions to NP-complete sets
• Autoreducibility, mitoticity, and immunity
• Hardness hypotheses, derandomization, and circuit complexity
• Diagonalizations over polynomial time computable sets
• On being incoherent without being very hard
• A comparison of polynomial time reducibilities
• Bi-immunity separates strong NP-completeness notions
• Non-uniform reductions
• Separating Complexity Classes Using Autoreducibility
• Separating NP-completeness notions under strong hypotheses

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