Paper by Erik D. Demaine
- 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.
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
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.
- This paper is also available from ScienceDirect.
- The paper is 6 pages.
- 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
Last updated January 4, 2022 by