Bi-immunity separates strong NP-completeness notions
DOI10.1016/J.IC.2003.05.001zbMATH Open1078.68042OpenAlexW1964450092MaRDI QIDQ1887166FDOQ1887166
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
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Cook reducibility is faster than Karp reducibility in NP
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Resource bounded randomness and weakly complete problems
- Separation of NP-completeness notions
- Separating NP-completeness notions under strong hypotheses
- A comparison of polynomial time reducibilities
- Lower Bounds for Selection in X + Y and Other Multisets
- Bi-immune sets for complexity classes
- Reductions on NP and p-selective sets
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
- Title not available (Why is that?)
- Partial bi-immunity, scaled dimension, and NP-completeness
- NP-completeness notions under strong hypotheses
- A thirty year old conjecture about promise problems
- Title not available (Why is that?)
- 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)
