3

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

Community
  • 1
Oleksandr Bondarenko
  • 4,215
  • 1
  • 25
  • 46
  • 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 06 '10 at 21:51
  • @Tsuyoushi I have edited the question to make it as specific as possible. – Oleksandr Bondarenko Dec 06 '10 at 22:25
  • 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 06 '10 at 22:32
  • 2
    I'm confused as to whether this question even makes sense. – Suresh Venkat Dec 06 '10 at 22:34
  • 1
    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 Dec 06 '10 at 22:39
  • @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 Dec 06 '10 at 23:07
  • 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 07 '10 at 03: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 07 '10 at 04:37
  • 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 Dec 07 '10 at 10:54
  • 1
    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 Dec 07 '10 at 23:05
  • @Peter Shor: If you think that your last comment answers my last question, could you, please, post it as the answer? – Oleksandr Bondarenko Dec 07 '10 at 23:20
  • @Tsuyoshi Ito: I'd like to close this question, since I can't delete it. – Oleksandr Bondarenko Dec 16 '10 at 15:48
  • 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 Dec 16 '10 at 15:55
  • 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. Aug 24 '12 at 16:29
  • 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. there is work to show even the slices are NP complete. – vzn Aug 24 '12 at 20:13

3 Answers3

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.

Peter Shor
  • 24,763
  • 4
  • 93
  • 133
7

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.

Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
  • @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 Dec 06 '10 at 22:55
  • @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 Dec 06 '10 at 23:05
  • 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 06 '10 at 23:06
  • Sadeq, I think you mean “unless P = NP”, right? – Antonio E. Porreca Dec 06 '10 at 23:11
  • @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 Dec 06 '10 at 23:18
  • @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 Dec 07 '10 at 00:00
  • @Antonio: yes, I meant “unless P = NP”. Thanks for pointing out. – Sadeq Dousti Dec 07 '10 at 00:06
  • @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 Dec 07 '10 at 00:12
  • @Sadeq: I decided to accept your answer since it gives the answer for the case without non-recognazibility. – Oleksandr Bondarenko Dec 07 '10 at 00:59
  • @Antonio: Could you, please, transform your first comment into an answer. – Oleksandr Bondarenko Dec 07 '10 at 01:01
  • The problem with your construction is the part "M determines the corresponding partition Πi". How can you do that given an instance? – Kaveh Aug 24 '12 at 02:14
  • @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 Aug 24 '12 at 08:10
  • @Sadeq, yes, I just want to point out that the original one does not work. :) – Kaveh Aug 24 '12 at 13:27
  • @Kaveh: OK, I'll rephrase my answer to clearly indicate this :) – Sadeq Dousti Aug 24 '12 at 13:48
  • 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 Aug 24 '12 at 14:00
  • 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 Aug 24 '12 at 14:50
  • @Sadeq, could you, please, answer on MCH's comment since I believe it makes sense. – Oleksandr Bondarenko Aug 24 '12 at 17:11
  • 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". – Mahdi Cheraghchi 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
3

Take a look at:

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

Joseph Malkevitch
  • 1,319
  • 6
  • 7
  • 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 06 '10 at 18:59