On universally easy classes for NP-complete problems.

DOI10.1016/S0304-3975(03)00286-XzbMATH Open1045.68065OpenAlexW2084955549MaRDI QIDQ1401418FDOQ1401418

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

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

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
• Complexity classes without machines: on complete languages for UP

zbMATH Keywords

Complexity theoryNP-completenessRegular languagesPolynomial 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)

Cites Work

• Graph Classes: A Survey
• Title not available (Why is that?)
• Scheduling jobs with fixed start and end times
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Title not available (Why is that?)
• Analytic models and ambiguity of context-free languages
• The growth function of context-free languages
• A characterization of poly-slender context-free languages
• Title not available (Why is that?)
• On universally easy classes for NP-complete problems

Cited In (4)

• ON UNIVERSALLY POLYNOMIAL CONTEXT-FREE LANGUAGES
• On the density of regular and context-free languages
• On universally easy classes for NP-complete problems
• 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 Q1401418)