On Universally Easy Classes for NP-complete Problems. E. D. Demaine, A. López-Ortiz and J. I. Munro. To appear Theoretical Computer Science, 2002. PostScript file.
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.