Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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."

share|cite|improve this question
I read revision 4. I find the question pretty vague, but I will wait to see how things will turn out before voting to close it. – Tsuyoshi Ito Dec 6 '10 at 21:51
If you ask for only a finite number of subsets, you can apply the algorithm for all of the subsets to an instance in polynomial time. If any of them gives a "yes" answer, the original instance must have a "yes" answer. Otherwise, it must have a "no" answer. Thus, if each of the finite number of subsets is solvable in polynomial time, their union is solvable in polynomial time. – Peter Shor Dec 6 '10 at 22:32
I'm confused as to whether this question even makes sense. – Suresh Venkat Dec 6 '10 at 22:34
I don't understand the question or the answers claiming that a positive answer would imply that the problem is in P. It seems to me that the answer to Oleksandr's question is trivially "yes": Take a decision problem where $\Pi$ represents the yes-instances. Then consider the partition $\Pi \cup \overline\Pi$. The problem is solvable in constant time when restricted to inputs from $\Pi$ (always answer yes), or when restricted to inputs from $\overline\Pi$ (always answer no). But $\Pi$ need not even be computable. – mikero Dec 7 '10 at 3:07
@mikero: I agree, and Peter pointed that out in his answer. The answers claiming that a positive answer would imply that the problem is in P seem to interpret “problem” as “language” and “partition of the problem” as “partition of the language,” but I do not think that that interpretation corresponds to the current question (revision 5). Anyway, I think that it is a moot point because the asker seems happy with the answer, which is a good thing. – Tsuyoshi Ito Dec 7 '10 at 4:37
up vote 7 down vote accepted

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.

share|cite|improve this answer
Oleksandr, no, that’s not a problem. Let $p_1, \ldots, p_n$ be polynomial upper bounds to the running time of $M_1, \ldots, M_n$ respectively. On input $x$, the machine $M$ can just run all machines $M_1, \ldots, M_n$ for up to $\max \{p_1(|x|), \ldots, p_n(|x|)\}$ steps each; if one of them accepts, then also $M$ does, and it rejects if all of them reject or fail to halt within that time bound. – Antonio E. Porreca Dec 6 '10 at 23:06
@MCH, @ Oleksandr: Please note that in my definition, $M_i$'s "decide" the corresponding partition $\Pi_i$, not merely "accept" it. (Consult Sipser's book, chapter 3). Therefore, $M_i$ outputs YES if and only if it is run on an input from $\Pi_i$. This means that $M_i$'s output on input from any other partition is not arbitrary; it is simply "NO". – M.S. Dousti Aug 24 '12 at 18:44
@Sadeq: The OP's question is up to interpretation. For example, by "solving" instances for graphs of degree 3, do you mean that inputs for graphs of degree other than 3 are rejected, or do we just don't care? If the partitioning assumption strictly requires rejection of invalid instances, then your argument is correct and the answer to Oleksandr's question is "No". Otherwise Peter Shor's argument is correct and the answer is "Yes". – MCH Aug 24 '12 at 20:14
@MCH: Yep. This is exactly what caused two different lines of reasoning, as described in OP's question. – M.S. Dousti Aug 24 '12 at 20:29
@MCH, the answer is also here. – Kaveh Aug 24 '12 at 21:49

If you partition the input into sets of instances, each of which has the same solution, then each of these sets of instances is indeed polynomial-time solvable. I'm sure this isn't what you're looking for, but I don't see how to naturally exclude it from your question.

share|cite|improve this answer
Thanks for your remark. Actually it is interesting how to exclude such cases from consideration. – Oleksandr Bondarenko Dec 6 '10 at 21:24
Seems that for search problems this argument won't work since I doubt there exists an NP-hard search problem that can be partitioned into sets of instances, each of which has the same solution. – Oleksandr Bondarenko Aug 24 '12 at 20:49

Take a look at:

share|cite|improve this answer
Thank you for the answer. I knew about that but now in virtue of your answer I can make my question more precise: what if we partition over different parameters? Are there known such partitions? – Oleksandr Bondarenko Dec 6 '10 at 18:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.