<p>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.</p>

<p>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.</p>

<p>This shows that $\Pi$ can be decided in poly-time, which is impossible unless $P = NP$.</p>

<p><strong>Edit:</strong> 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.</p>

CC BY-SA 2.5
2010-12-06T22:55:51.167Z
@Sadeq Thank you for your definitive answer. Taking into account that $\Pi_i$ can be not polynomially recognizable then can it be that $M$ uses exponential time to determine to what $\Pi_i$ input $x$ belongs?
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-06T23:05:37.617Z
@Oleksandr: Can you give an example? In the **maximal degree** example you gave in the question, non-recognizability is certainly not the case.
Sadeq Dousti
CC BY-SA 2.5
2010-12-06T23:06:15.760Z
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
CC BY-SA 2.5
2010-12-06T23:11:54.957Z
Sadeq, I think you mean “unless P = NP”, right?
Antonio E. Porreca
CC BY-SA 2.5
2010-12-06T23:18:51.617Z
@Sadeq I could give an example with exponential recognizability but I'm not sure that I could give appropriate partition for the example's superproblem.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-07T00:00:05.610Z
@Antonio If $n$ is superpolynomial in the size of the input $x$ and at least one case is superpolynomially recognizable, then at the worst case $M$ should run superpolynomial number $n$ of machines. So it follows that with finite but superpolynomial number of cases there's no guarantee that we'll solve $\Pi$ in polynomial time in the size of the input $x$.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-07T00:06:35.047Z
@Antonio: yes, I meant “unless P = NP”. Thanks for pointing out.
Sadeq Dousti
CC BY-SA 2.5
2010-12-07T00:12:21.043Z
@Oleksandr: $n$ cannot depend on the size of input. When you say the partition is finite, it means that $n$ is a fixed constant.
Sadeq Dousti
CC BY-SA 2.5
2010-12-07T00:59:23.407Z
@Sadeq: I decided to accept your answer since it gives the answer for the case without non-recognazibility.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-07T01:01:30.800Z
@Antonio: Could you, please, transform your first comment into an answer.
Oleksandr Bondarenko
CC BY-SA 3.0
2012-08-24T02:14:27.703Z
The problem with your construction is the part "M determines the corresponding partition Πi". How can you do that given an instance?
Kaveh
CC BY-SA 3.0
2012-08-24T08:10:12.473Z
@Kaveh: I think your question has already been answered by Antonio's comment above, and described in my "edit" above: "It does not need to recognize the partition..."
Sadeq Dousti
CC BY-SA 3.0
2012-08-24T13:27:27.603Z
@Sadeq, yes, I just want to point out that the original one does not work. :)
Kaveh
CC BY-SA 3.0
2012-08-24T13:48:29.373Z
@Kaveh: OK, I'll rephrase my answer to clearly indicate this :)
Sadeq Dousti
CC BY-SA 3.0
2012-08-24T14:00:57.060Z
I don't think that works even considering Antonio's comment. Each machine is promised to work properly for their respective set of instances, but in general can behave arbitrarily otherwise. So first of all we may not be able to decide which machine is related to a given instance, and moreover, if we run all machines and see which one accepts, we may see an accept from a machine that the instance does not belong to, which would be perfectly fine but not what we want. I think Peter Shor's answer "trivially yes" is correct.
Mahdi Cheraghchi
CC BY-SA 3.0
2012-08-24T14:50:43.763Z
it would seem that so far people are answering this question not wrt coNP. taking into account solutions wrt coNP might clarify the problem. the original problem seems phrased inexactly. what exactly is meant by "polynomially solvable but not polynomially recognizable" in the original problem? the complement of P is also P. which is highly relevant to the P vs NP problem because if coNP != NP it is proven that P != NP.
vzn
CC BY-SA 3.0
2012-08-24T17:11:46.833Z
@Sadeq, could you, please, answer on MCH's comment since I believe it makes sense.
Oleksandr Bondarenko
CC BY-SA 3.0
2012-08-24T18:44:48.240Z
@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".
Sadeq Dousti
CC BY-SA 3.0
2012-08-24T20:14:26.507Z
@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".
Mahdi Cheraghchi
CC BY-SA 3.0
2012-08-24T20:29:59.707Z
@MCH: Yep. This is exactly what caused two different lines of reasoning, as described in OP's question.
Sadeq Dousti
CC BY-SA 3.0
2012-08-24T21:49:17.050Z
@MCH, the answer is also [here](http://math.stackexchange.com/q/15231/468).
Kaveh
CC BY-SA 3.0
2010-12-06T22:31:38.813Z
2012-08-24T13:50:12.710Z
2012-08-24T13:50:12.710Z
Sadeq Dousti
<p>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.</p>

CC BY-SA 3.0
2012-08-24T20:49:37.800Z
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
CC BY-SA 2.5
2010-12-06T21:24:02.200Z
Thanks for your remark. Actually it is interesting how to exclude such cases from consideration.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-06T21:15:51.887Z
2010-12-06T21:15:51.887Z
Peter Shor 
<p>Take a look at:</p>

<p><a href="http://en.wikipedia.org/wiki/Parameterized_complexity" rel="nofollow">http://en.wikipedia.org/wiki/Parameterized_complexity</a></p>

CC BY-SA 2.5
2010-12-06T18:59:09.407Z
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
CC BY-SA 2.5
2010-12-06T18:50:32.910Z
2010-12-06T18:50:32.910Z
Joseph Malkevitch
<p>Let <span class="math-container">$\Pi$</span> be NP-complete problem.</p>
<p>Can we partition set of instances of <span class="math-container">$\Pi$</span> into finite number of subsets (subproblems) each of which is polynomially solvable (and not necessarily polynomially recognizable)?</p>
<p>For example, <span class="math-container">$\Pi$</span> is NP-complete for graphs with maximal degree <span class="math-container">$\Delta=3$</span>, but polynomially solvable for cubic and graphs with <span class="math-container">$\Delta=2$</span>?</p>
<blockquote>
<p>I have obtained two answers on my question: &quot;trivially yes&quot; (by Peter Shor and mikero) and no, unless <span class="math-container">$P=NP$</span> (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:</p>
<p>how to formulate two questions such that for each of them corresponding answers would hold.</p>
</blockquote>
<hr />
<p>The last edition of this question has been answered in full by Peter Shor on Math.SE <a href="https://math.stackexchange.com/questions/15231/can-we-partition-np-complete-problem-into-finite-number-of-polynomially-solvable">here</a>.</p>
<p>Here is the answer:</p>
<blockquote>
<p>&quot;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 &quot;yes&quot; cases or (b) just require the computer to give you the answer.&quot;</p>
</blockquote>

CC BY-SA 3.0
2012-08-24T16:29:45.587Z
When partitioning your problem down, would you not be creating a greedy/locally optimal solution? That could definitely change your complete solution from NP to P.
Josh C.
CC BY-SA 3.0
2012-08-24T20:13:28.720Z
special case of this problem: there are indeed apparently relatively "large" classes of P-time solvable inputs for NP complete problems. eg, 2SAT. or k-clique for any fixed k. etcetera. but these partitions cannot ever be "big enough" to "cover" the NP-complete problem unless P==NP. also, note another std way to partition NP complete problems is by "slice functions" which count the # of 1s ("weight") in the inputs. see eg [hardness of parameterized clique](http://cstheory.stackexchange.com/questions/1441/hardness-of-parameterized-clique). there is work to show even the slices are NP complete.
vzn
CC BY-SA 2.5
2010-12-06T21:51:33.470Z
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
CC BY-SA 2.5
2010-12-06T22:25:37.527Z
@Tsuyoushi I have edited the question to make it as specific as possible.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-06T22:32:34.383Z
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 
CC BY-SA 2.5
2010-12-06T22:34:02.243Z
I'm confused as to whether this question even makes sense.
Suresh Venkat
CC BY-SA 2.5
2010-12-06T22:39:15.100Z
I think it would be better if you think a little bit more about what you want to know and why you are interested in knowing it and then modify the question accordingly. And there is no need to hurry, the question can be reopened if it gets closed.
Kaveh
CC BY-SA 2.5
2010-12-06T23:07:27.913Z
@Peter It seems to me that either you didn't understand the question or it's me who don't understand your answer: I asked not about subsets of an instance of a problem $\Pi$, but about subsets of instances of problem $\Pi$.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-07T03:07:58.480Z
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
CC BY-SA 2.5
2010-12-07T04:37:57.487Z
@mikero: I agree, and Peter pointed that out in [his answer](http://cstheory.stackexchange.com/questions/3592/can-we-partition-np-complete-problem-into-finite-number-of-polynomially-solvable/3601#3601).  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
CC BY-SA 2.5
2010-12-07T10:54:57.897Z
Thanks to the comments of mikero and Tsuyoshi I understood that the answer of Peter can be regarded as the correct answer to my question so I'll accept it. And I like the answer of Mikero.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-07T23:05:01.647Z
There's a crucial point left out. Does the algorithm which solves the problem for each of the finite subsets have to produce a witness for the NP-completeness in a yes instance, or can it just answer "yes" or "no"? This is the difference between mikero's comment and Antonio's tweak of Sadeq's answer.
Peter Shor 
CC BY-SA 2.5
2010-12-07T23:20:47.727Z
@Peter Shor: If you think that your last comment answers my last question, could you, please, post it as the answer?
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-16T15:48:07.473Z
@Tsuyoshi Ito: I'd like to close this question, since I can't delete it.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-16T15:55:00.547Z
I think that you can vote to close it, but I am not sure if you should.  At least several people posted answers, which means that they thought the question was worth answering, implying that it may not be good to close the question.  Another option is to accept the answer you think is the best and go forward.
Tsuyoshi Ito
<cc.complexity-theory>
Can we partition NP-complete problem into finite number of polynomially solvable problems?
Oleksandr Bondarenko
# Can we partition NP-complete problem into finite number of polynomially solvable problems?

(Asked by: username_0 on 2010-12-06)

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 username_4and username_7) and no, unless $P=NP$ (by username_8 and username_9). 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 username_4on Math.SE [here](https://math.stackexchange.com/questions/15231/can-we-partition-np-complete-problem-into-finite-number-of-polynomially-solvable).

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

**Tags:** cc.complexity-theory

> **Comments:**
> **username_3**: 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.  
> **username_0**: @Tsuyoushi I have edited the question to make it as specific as possible.  
> **username_4**: 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.  
> **username_5**: I'm confused as to whether this question even makes sense.  
> **username_6**: I think it would be better if you think a little bit more about what you want to know and why you are interested in knowing it and then modify the question accordingly. And there is no need to hurry, the question can be reopened if it gets closed.  
> **username_0**: @Peter It seems to me that either you didn't understand the question or it's me who don't understand your answer: I asked not about subsets of an instance of a problem $\Pi$, but about subsets of instances of problem $\Pi$.  
> **username_7**: 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.  
> **username_3**: @username_7: I agree, and Peter pointed that out in [his answer](http://cstheory.stackexchange.com/questions/3592/can-we-partition-np-complete-problem-into-finite-number-of-polynomially-solvable/3601#3601).  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.  
> **username_0**: Thanks to the comments of username_7 and Tsuyoshi I understood that the answer of Peter can be regarded as the correct answer to my question so I'll accept it. And I like the answer of Mikero.  
> **username_4**: There's a crucial point left out. Does the algorithm which solves the problem for each of the finite subsets have to produce a witness for the NP-completeness in a yes instance, or can it just answer "yes" or "no"? This is the difference between username_7's comment and Antonio's tweak of Sadeq's answer.  
> **username_0**: @Peter Shor: If you think that your last comment answers my last question, could you, please, post it as the answer?  
> **username_0**: @username_3: I'd like to close this question, since I can't delete it.  
> **username_3**: I think that you can vote to close it, but I am not sure if you should.  At least several people posted answers, which means that they thought the question was worth answering, implying that it may not be good to close the question.  Another option is to accept the answer you think is the best and go forward.  
> **username_1**: When partitioning your problem down, would you not be creating a greedy/locally optimal solution? That could definitely change your complete solution from NP to P.  
> **username_2**: special case of this problem: there are indeed apparently relatively "large" classes of P-time solvable inputs for NP complete problems. eg, 2SAT. or k-clique for any fixed k. etcetera. but these partitions cannot ever be "big enough" to "cover" the NP-complete problem unless P==NP. also, note another std way to partition NP complete problems is by "slice functions" which count the # of 1s ("weight") in the inputs. see eg [hardness of parameterized clique](http://cstheory.stackexchange.com/questions/1441/hardness-of-parameterized-clique). there is work to show even the slices are NP complete.  

---

## 3 answers

### Answer by username_8 on 2010-12-06. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: @Sadeq Thank you for your definitive answer. Taking into account that $\Pi_i$ can be not polynomially recognizable then can it be that $M$ uses exponential time to determine to what $\Pi_i$ input $x$ belongs?  
> **username_8**: @Oleksandr: Can you give an example? In the **maximal degree** example you gave in the question, non-recognizability is certainly not the case.  
> **username_9**: 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.  
> **username_9**: Sadeq, I think you mean “unless P = NP”, right?  
> **username_0**: @Sadeq I could give an example with exponential recognizability but I'm not sure that I could give appropriate partition for the example's superproblem.  
> **username_0**: @Antonio If $n$ is superpolynomial in the size of the input $x$ and at least one case is superpolynomially recognizable, then at the worst case $M$ should run superpolynomial number $n$ of machines. So it follows that with finite but superpolynomial number of cases there's no guarantee that we'll solve $\Pi$ in polynomial time in the size of the input $x$.  
> **username_8**: @Antonio: yes, I meant “unless P = NP”. Thanks for pointing out.  
> **username_8**: @Oleksandr: $n$ cannot depend on the size of input. When you say the partition is finite, it means that $n$ is a fixed constant.  
> **username_0**: @Sadeq: I decided to accept your answer since it gives the answer for the case without non-recognazibility.  
> **username_0**: @Antonio: Could you, please, transform your first comment into an answer.  
> **username_6**: The problem with your construction is the part "M determines the corresponding partition Πi". How can you do that given an instance?  
> **username_8**: @username_6: I think your question has already been answered by Antonio's comment above, and described in my "edit" above: "It does not need to recognize the partition..."  
> **username_6**: @Sadeq, yes, I just want to point out that the original one does not work. :)  
> **username_8**: @username_6: OK, I'll rephrase my answer to clearly indicate this :)  
> **username_10**: I don't think that works even considering Antonio's comment. Each machine is promised to work properly for their respective set of instances, but in general can behave arbitrarily otherwise. So first of all we may not be able to decide which machine is related to a given instance, and moreover, if we run all machines and see which one accepts, we may see an accept from a machine that the instance does not belong to, which would be perfectly fine but not what we want. I think Peter Shor's answer "trivially yes" is correct.  
> **username_2**: it would seem that so far people are answering this question not wrt coNP. taking into account solutions wrt coNP might clarify the problem. the original problem seems phrased inexactly. what exactly is meant by "polynomially solvable but not polynomially recognizable" in the original problem? the complement of P is also P. which is highly relevant to the P vs NP problem because if coNP != NP it is proven that P != NP.  
> **username_0**: @Sadeq, could you, please, answer on MCH's comment since I believe it makes sense.  
> **username_8**: @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".  
> **username_10**: @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".  
> **username_8**: @MCH: Yep. This is exactly what caused two different lines of reasoning, as described in OP's question.  
> **username_6**: @MCH, the answer is also [here](http://math.stackexchange.com/q/15231/468).  

---

### Answer by username_4 on 2010-12-06. Score: 8

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.

> **Comments:**
> **username_0**: Thanks for your remark. Actually it is interesting how to exclude such cases from consideration.  
> **username_0**: 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`.  

---

### Answer by username_11 on 2010-12-06. Score: 3

Take a look at:

<http://en.wikipedia.org/wiki/Parameterized_complexity>

> **Comments:**
> **username_0**: 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?  

---

