3
$\begingroup$

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

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Dec 6, 2010 at 21:51
  • 6
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Dec 6, 2010 at 22:32
  • 2
    $\begingroup$ I'm confused as to whether this question even makes sense. $\endgroup$
    – Suresh Venkat
    Dec 6, 2010 at 22:34
  • 3
    $\begingroup$ 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. $\endgroup$
    – mikero
    Dec 7, 2010 at 3:07
  • 2
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Dec 7, 2010 at 4:37

3 Answers 3

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
21
  • 4
    $\begingroup$ 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. $\endgroup$
    – Antonio E. Porreca
    Dec 6, 2010 at 23:06
  • 1
    $\begingroup$ @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". $\endgroup$
    – Sadeq Dousti
    Aug 24, 2012 at 18:44
  • 1
    $\begingroup$ @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". $\endgroup$
    – Mahdi Cheraghchi
    Aug 24, 2012 at 20:14
  • 1
    $\begingroup$ @MCH: Yep. This is exactly what caused two different lines of reasoning, as described in OP's question. $\endgroup$
    – Sadeq Dousti
    Aug 24, 2012 at 20:29
  • 1
    $\begingroup$ @MCH, the answer is also here. $\endgroup$
    – Kaveh
    Aug 24, 2012 at 21:49
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your remark. Actually it is interesting how to exclude such cases from consideration. $\endgroup$
    – Oleksandr Bondarenko
    Dec 6, 2010 at 21:24
  • $\begingroup$ 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. $\endgroup$
    – Oleksandr Bondarenko
    Aug 24, 2012 at 20:49
3
$\begingroup$

Take a look at:

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Oleksandr Bondarenko
    Dec 6, 2010 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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