Bi-immunity separates strong NP-completeness notions

DOI10.1016/j.ic.2003.05.001zbMath1078.68042OpenAlexW1964450092MaRDI QIDQ1887166

A. Pavan, Selman, Alan L.

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)

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