On universally easy classes for NP-complete problems

MaRDI QIDQ2768398zbMATH OpenFDO

Authors Erik D. Demaine, J. Ian Munro, Alejandro Lopez-Ortiz

Publication date 30 January 2002

zbMATH Keywords

NP-complete problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• On universally easy classes for NP-complete problems.
• scientific article; zbMATH DE number 1796949
• ON UNIVERSALLY POLYNOMIAL CONTEXT-FREE LANGUAGES
• Universal resolution for NP-complete problems
• NP-hard graph problems and boundary classes of graphs

Cited in

(6)

• NP is as easy as detecting unique solutions
• Universal resolution for NP-complete problems
• On universally easy classes for NP-complete problems.
• ON UNIVERSALLY POLYNOMIAL CONTEXT-FREE LANGUAGES
• scientific article; zbMATH DE number 3845080 (Why is no real title available?)
• Easy NP-hardness Proofs of Some Subset Choice Problems

This page was built for publication: On universally easy classes for NP-complete problems

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