Separating Cook completeness from Karp-Levin completeness under a worst-case hardness hypothesis

DOI10.4230/LIPICS.FSTTCS.2014.445MaRDI QIDQ2978535zbMATH OpenOpenAlexFDO

Authors Debasis Mandal, Aduri Pavan, Rajeswari Venugopalan

Publication date 25 April 2017

Full work available at URL http://drops.dagstuhl.de/opus/volltexte/2014/4862/

zbMATH Keywords

Cook reductionKarp reductionmany-one completenessNP-completenessTuring completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• Separation of NP-completeness notions
• NP-completeness notions under strong hypotheses

Cited in

(4)

• Partial bi-immunity, scaled dimension, and NP-completeness
• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Collapsing and separating completeness notions under average-case and worst-case hypotheses

This page was built for publication: Separating Cook completeness from Karp-Levin completeness under a worst-case hardness hypothesis

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