Separating NP-completeness notions under strong hypotheses

DOI10.1006/JCSS.1999.1674MaRDI QIDQ5929911zbMATH OpenOpenAlexFDO

Authors Klaus Ambos-Spies, Levke Bentzien

Publication date 17 April 2001

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.1999.1674

zbMATH Keywords

NP-\(m\)-completenessNP-\(T\)-completenessNP-completeness

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• NP-completeness notions under strong hypotheses
• Comparing reductions to NP-complete sets
• Separation of NP-completeness notions
• Comparing Reductions to NP-Complete Sets
• Cook versus Karp-Levin: Separating completeness notions if NP is not small

Cited in

(20)

• On strong NP-completeness of rational problems
• Autoreducibility of NP-complete sets under strong hypotheses
• Bi-immunity separates strong NP-completeness notions
• Hard sets are hard to find
• Query-monotonic Turing reductions
• Partial bi-immunity, scaled dimension, and NP-completeness
• NP-completeness notions under strong hypotheses
• Separation of NP-completeness notions
• A thirty year old conjecture about promise problems
• scientific article; zbMATH DE number 176522 (Why is no real title available?)
• scientific article; zbMATH DE number 2086403 (Why is no real title available?)
• scientific article; zbMATH DE number 7599997 (Why is no real title available?)
• scientific article; zbMATH DE number 2201364 (Why is no real title available?)
• The size of SPP
• Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• If not empty, NP-P is topologically large
• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• Inseparability and strong hypotheses for disjoint NP pairs
• Comparing reductions to NP-complete sets

This page was built for publication: Separating NP-completeness notions under strong hypotheses

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