Can we partition NP-complete problem into finite number of polynomially solvable problems?

Question

I have asked this question on cstheory.

Let $\Pi$ be NP-complete problem.

Can we partition the set of instances of $\Pi$ into finite number of subsets (subproblems) each of which is polynomially solvable (and not necessarily polynomially recognizable)?

On cstheory I have obtained two answers on my question: "trivially yes" and no, unless $P=NP$. Trivially yes, since we could just take the sets of instances with equal value of objective function for each of subset. And no, since if we had such subproblems then we could solve the general problem, but that's not possible unless $P=NP$. So the question is:

how to formulate two questions such that for each of them corresponding answers would hold.

Answer 1

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.

Suppose you are just asking for the answer, as in (b). Then you can partition the set of instances of $\Pi$ into "yes" instances and "no" instances. For each set of instances, there is a one-line program which gives you the answer for that set of instances. So in this case, the answer to your question is "yes."

Now, suppose, as in (a), you require a witness in the "yes" cases as well as the answer. Let the algorithms for the different subclasses be $A_1$, $A_2$, $A_3$, $\ldots$, $A_k$. Now we give a master algorithm $A$ that, given an instance $x$, runs all $k$ algorithms on it. $A$ checks the witnesses that the algorithms $A_i$ output to see whether one of them verifies that $x$ is a "yes" instances. If one of them does, then $A$ outputs "yes". Otherwise, $A$ outputs "no".

If $x$ is a "yes" instance, one of the algorithms $A_i$ must output a valid witness, and so $A$ will accept. If $x$ is a "no" instance, there are no valid witnesses, and so $A$ will reject. Thus, for case (a), if the answer to your question is "yes", $A$ solves an NP-complete problem in polynomial time, and we have P$=$NP.

None of this argument is original; I'm just consolidating and summarizing the answers that this question got on cstheory.

Answer 2

If you allow exponentially many machines and each can know its serial number, try this. For travelling salesman, you have n! machines. Each one attempts to verify the cost of a trip for a given permutation, generated in a reasonable way from its serial number. This can be done in polynomial time. Each machine raises a bit if it succeeds. Can't you then combine these in log(n!) time, which is polynomial. You are still doing exponentially much computation, but spreading it over many machines.

Answer 3

The question is what do you exactly mean by "solving a partition" of a problem.

In Peter's answer on cstheory, the question is interpreted as "given an instance from the partition output the answer on that instance".

In Sadeq's answer, the question is interpreted as "given an instance, output the answer on that instance if it is in the partition, otherwise reject", if the problem is a decision problem, this becomes "decide the partition".

In short Peter is interpreting the question as a promise problem while Sadeq is interpreting it as deciding the partitions.

If you decide the partitions, you can combine them with OR to obtain the answer. However if you are deciding the promise version you cannot do this because the answer of each machine on instances that do not belong to that partition is not defined, so taking OR will not work.