Bi-immunity separates strong NP-completeness notions

DOI10.1016/J.IC.2003.05.001MaRDI QIDQ1887166zbMATH OpenOpenAlexFDO

Authors Aduri Pavan, Alan L. Selman

Publication date 23 November 2004

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2003.05.001

zbMATH Keywords

Turing completenessBi-immunityMany-one completeness

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)

Recommendations

• scientific article; zbMATH DE number 2086403
• Partial bi-immunity, scaled dimension, and NP-completeness
• Separating NP-completeness notions under strong hypotheses
• Properties of NP‐Complete Sets
• Separation of NP-completeness notions

Cites work

• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• A comparison of polynomial time reducibilities
• Bi-immune sets for complexity classes
• Cook reducibility is faster than Karp reducibility in NP
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Lower Bounds for Selection in X + Y and Other Multisets
• Reductions on NP and p-selective sets
• Resource bounded randomness and weakly complete problems
• Separating NP-completeness notions under strong hypotheses
• Separation of NP-completeness notions

Cited in

(11)

• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• Comparing reductions to NP-complete sets
• Autoreducibility of NP-complete sets under strong hypotheses
• Bi-immune sets for complexity classes
• Partial bi-immunity, scaled dimension, and NP-completeness
• NP-completeness notions under strong hypotheses
• A thirty year old conjecture about promise problems
• scientific article; zbMATH DE number 2086403 (Why is no real title available?)
• Nonuniform reductions and NP-completeness
• Nonuniform reductions and NP-completeness
• Properties of NP‐Complete Sets

This page was built for publication: Bi-immunity separates strong NP-completeness notions

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