Let $\Pi$ be NP-complete problem.
Can we partition set of instances of $\Pi$ into finite number of subsets (subproblems) each of which is polynomially solvable (and not necessarily polynomially recognizable)?
For example, $\Pi$ is NP-complete for graphs with maximal degree $\Delta=3$, but polynomially solvable for cubic and graphs with $\Delta=2$?
I have obtained two answers on my question: "trivially yes" (by Peter Shor and mikero) and no, unless $P=NP$ (by Sadeq Dousti and Antonio E. Porreca). I'm curious why such easy question gets such contradicting answers (not taking into account the reason that I have formulated it ambiguously). So the question is:
how to formulate two questions such that for each of them corresponding answers would hold.
The last edition of this question has been answered in full by Peter Shor on Math.SE here.
Here is the answer:
"There are two different possible questions here. When you ask for the solution of an NP-complete problem, you can either (a) require the computer to give you a witness in the "yes" cases or (b) just require the computer to give you the answer."