Paper by Erik D. Demaine
- Reference:
- Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro, “On Universally Easy Classes for NP-complete Problems”, Theoretical Computer Science, volume 304, number 1–3, July 2003, pages 471–476.
- Abstract:
-
We explore the natural question of whether all NP-complete problems have
a common restriction under which they are polynomially solvable. More
precisely, we study what languages are universally easy in that their
intersection with any NP-complete problem is in P
(universally polynomial) or at least no longer NP-complete
(universally simplifying).
In particular, we give a polynomial-time algorithm to determine whether a
regular language is universally easy.
While our approach is language-theoretic, the results
bear directly on finding polynomial-time solutions to very broad and useful
classes of problems.
- Comments:
- This paper is also available from ScienceDirect.
- Length:
- The paper is 6 pages.
- Availability:
- The paper is available in PostScript (263k), gzipped PostScript (124k), and PDF (113k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- SODA2001c (On Universally Easy Classes for NP-complete Problems)
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.