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”, in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), Washington, DC, January 7–9, 2001, pages 910–911.

BibTeX

@InProceedings{SODA2001c,
  AUTHOR        = {Erik D. Demaine and Alejandro L\'opez-Ortiz and
                   J. Ian Munro},
  TITLE         = {On Universally Easy Classes for NP-complete Problems},
  BOOKTITLE     = {Proceedings of the 12th Annual ACM-SIAM Symposium on
                   Discrete Algorithms (SODA 2001)},
  BOOKURL       = {http://www.siam.org/meetings/da01/},
  ADDRESS       = {Washington, DC},
  MONTH         = {January 7--9},
  YEAR          = 2001,
  PAGES         = {910--911},

  LENGTH        = {2 pages},
  PAPERS        = {UniversallyEasy_TCS},
  dblp          = {https://dblp.org/rec/conf/soda/DemaineLM01},
  ee            = {http://dl.acm.org/citation.cfm?id=365411.365806},
}

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

Length:

The paper is 2 pages.

Availability:

The paper is available in PostScript (111k) and gzipped PostScript (47k).

See information on file formats.

[Google Scholar search]

Related papers:

UniversallyEasy_TCS (On Universally Easy Classes for NP-complete Problems)