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 (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.

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 BibTeX file.
Last updated March 12, 2024 by Erik Demaine.