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.