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

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.