On universally easy classes for NP-complete problems.

DOI10.1016/S0304-3975(03)00286-XzbMath1045.68065OpenAlexW2084955549MaRDI QIDQ1401418

J. Ian Munro, Alejandro López-Ortiz, Erik D. Demaine

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00286-x

zbMATH Keywords

NP-completenessRegular languagesComplexity theoryPolynomial timeClasses of instancesUniversally polynomialUniversally simplifying

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

ON THE DENSITY OF REGULAR AND CONTEXT-FREE LANGUAGES

Cites Work

• Analytic models and ambiguity of context-free languages
• Scheduling jobs with fixed start and end times
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Graph Classes: A Survey
• A characterization of poly-slender context-free languages
• The growth function of context-free languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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