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.

BibTeX

@Article{UniversallyEasy_TCS,
  AUTHOR        = {Erik D. Demaine and Alejandro L\'opez-Ortiz and J. Ian
                   Munro},
  TITLE         = {On Universally Easy Classes for NP-complete Problems},
  JOURNAL       = {Theoretical Computer Science},
  journalurl    = {https://www.journals.elsevier.com/theoretical-computer-science},
  VOLUME        = 304,
  NUMBER        = {1--3},
  MONTH         = {July},
  YEAR          = 2003,
  PAGES         = {471--476},

  papers        = {SODA2001c},
  replaces      = {SODA2001c},
  length        = {6 pages},
  doi           = {https://dx.doi.org/10.1016/S0304-3975(03)00286-X},
  dblp          = {https://dblp.org/rec/journals/tcs/DemaineLM03},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1016/S0304-3975(03)00286-X">ScienceDirect</A>.},
}

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)