Paper by Erik D. Demaine
- 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.
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.
- The paper is 2 pages.
- 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 6, 2023 by