Separation of NP-Completeness Notions

DOI10.1137/S0097539701387039zbMath1017.68054OpenAlexW2070692345MaRDI QIDQ2784487

A. Pavan, Selman, Alan L.

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

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

Mathematics Subject Classification ID

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

Related Items (11)

Bi-immunity separates strong NP-completeness notions ⋮ Query-monotonic Turing reductions ⋮ Reductions between disjoint NP-pairs ⋮ A thirty year old conjecture about promise problems ⋮ Comparing reductions to NP-complete sets ⋮ Autoreducibility, mitoticity, and immunity ⋮ On the relative power of reduction notions in arithmetic circuit complexity ⋮ Upward separations and weaker hypotheses in resource-bounded measure ⋮ Collapsing and separating completeness notions under average-case and worst-case hypotheses ⋮ Non-mitotic Sets ⋮ Non-mitotic sets

This page was built for publication: Separation of NP-Completeness Notions