Take the 2-minute tour ×
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.

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|improve this question
1  
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
6  
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
2  
I'm confused as to whether this question even makes sense. –  Suresh Venkat Dec 6 '10 at 22:34
3  
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
2  
@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
show 11 more comments

3 Answers

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|improve this answer
4  
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
1  
@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 Aug 24 '12 at 18:44
1  
@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
1  
@MCH: Yep. This is exactly what caused two different lines of reasoning, as described in OP's question. –  Sadeq Dousti Aug 24 '12 at 20:29
1  
@MCH, the answer is also here. –  Kaveh Aug 24 '12 at 21:49
show 18 more comments

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|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
add comment

Take a look at:

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

share|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
add comment

Your Answer

 
discard

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.