Separation of NP-completeness notions

DOI10.1137/S0097539701387039MaRDI QIDQ2784487zbMATH OpenOpenAlexFDO

Authors Aduri Pavan, Alan L. Selman

Publication date 23 April 2002

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539701387039

zbMATH Keywords

\(p\)-genericity\(p\)-selectivitymany-one completenesstruth-table completenessTuring completeness

Mathematics Subject Classification ID

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

Recommendations

• Separating NP-completeness notions under strong hypotheses
• NP-Completeness, Proof Systems, and Disjoint NP-Pairs.
• Splitting NP-Complete Sets
• NP-completeness notions under strong hypotheses
• Separation of deterministic, nondeterministic and alternating complexity classes
• NP-completeness of the Planar Separator Problems
• Decidability of NP-complete problems
• scientific article; zbMATH DE number 3883607
• scientific article; zbMATH DE number 4077187
• NP-completeness: a retrospective

Cited in

(23)

• Non-mitotic sets
• Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
• On the relative power of reduction notions in arithmetic circuit complexity
• Bi-immunity separates strong NP-completeness notions
• Separation of the monotone NC hierarchy
• Query-monotonic Turing reductions
• Reductions between disjoint NP-pairs
• Upward separations and weaker hypotheses in resource-bounded measure
• Partial bi-immunity, scaled dimension, and NP-completeness
• NP-completeness notions under strong hypotheses
• Separating Cook completeness from Karp-Levin completeness under a worst-case hardness hypothesis
• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• A thirty year old conjecture about promise problems
• scientific article; zbMATH DE number 5320331 (Why is no real title available?)
• scientific article; zbMATH DE number 1222582 (Why is no real title available?)
• scientific article; zbMATH DE number 2086403 (Why is no real title available?)
• Non-mitotic Sets
• On Some $\mathcal{NP}$ -complete SEFE Problems
• Separating NP-completeness notions under strong hypotheses
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• Comparing reductions to NP-complete sets
• Autoreducibility, mitoticity, and immunity

This page was built for publication: Separation of NP-completeness notions

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