Bi-immunity separates strong NP-completeness notions
From MaRDI portal
Publication:1887166
DOI10.1016/j.ic.2003.05.001zbMath1078.68042OpenAlexW1964450092MaRDI QIDQ1887166
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (7)
Unnamed Item ⋮ Nonuniform reductions and NP-completeness ⋮ A thirty year old conjecture about promise problems ⋮ Comparing reductions to NP-complete sets ⋮ Autoreducibility of NP-complete sets under strong hypotheses ⋮ Partial bi-immunity, scaled dimension, and NP-completeness ⋮ Collapsing and separating completeness notions under average-case and worst-case hypotheses
Cites Work
- Unnamed Item
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Cook reducibility is faster than Karp reducibility in NP
- Reductions on NP and p-selective sets
- A comparison of polynomial time reducibilities
- Resource bounded randomness and weakly complete problems
- Separation of NP-Completeness Notions
- Bi-immune sets for complexity classes
- Lower Bounds for Selection in X + Y and Other Multisets
- Separating NP-completeness notions under strong hypotheses
This page was built for publication: Bi-immunity separates strong NP-completeness notions