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.
Can we partition NP-complete problem into finite number of polynomially solvable problems?
cc.complexity theory
Let $\Pi = \{\Pi_1, \ldots, \Pi_n\}$ be the finite partition of problem $\Pi$. Let $M_1, \ldots, M_n$ be the poly-time machines which decide the corresponding partition.Since the partition is finite, we can construct a poly-time machine $M$ which incorporates the code of $M_1, \ldots, M_n$. On input $x \in \Pi_i$, $M$ determines the corresponding partition $\Pi_i$, and calls the respective machine $M_i$ to decide it.This shows that $\Pi$ can be decided in poly-time, which is impossible unless $P = NP$.Edit: The above approach is incorrect in that $M$ may not be able to determine the correct partition. The right approach is given by Antonio in a comment bellow. It does not need to recognize the partition; instead, it just runs all $M_i$'s on $x$ an accepts if and only if at least one of them accepts.