1
$\begingroup$

I have asked this question on cstheory.

Let $\Pi$ be NP-complete problem.

Can we partition the set of instances of $\Pi$ into finite number of subsets (subproblems) each of which is polynomially solvable (and not necessarily polynomially recognizable)?

On cstheory I have obtained two answers on my question: "trivially yes" and no, unless $P=NP$. Trivially yes, since we could just take the sets of instances with equal value of objective function for each of subset. And no, since if we had such subproblems then we could solve the general problem, but that's not possible unless $P=NP$. So the question is:

how to formulate two questions such that for each of them corresponding answers would hold.

$\endgroup$
17
  • 1
    $\begingroup$ You seem to already be aware of the issue here: even if you know that such a partition exists, you need a second algorithm to recognize which subproblem you're in. $\endgroup$
    – Qiaochu Yuan
    Dec 22, 2010 at 19:09
  • $\begingroup$ That's not essentially the problem, since if we have a polynomial algorithm for each of the finite number of subproblems, we could just run them one after another and this took polynomial time as well. $\endgroup$
    – Oleksandr Bondarenko
    Dec 22, 2010 at 19:13
  • 1
    $\begingroup$ @Oleksandr While, running a finite number of polynomial time algorithms requires only polynomial time we don't know which answer is correct. For example, we can partition all instances of 3-Sat into two sets: YES and NO, where YES contains all instances that are satsifiable and NO contains all instances that are unsatisfiable. Trivially, all problems in YES can be solved in polynomial time by the Turing Machine (TM) that just accepts and all problems in NO can be solved in polynomial time by the TM that just rejects. However, this tells us nothing about whether a given instance is satisfiable. $\endgroup$
    – Travis Service
    Dec 22, 2010 at 19:42
  • $\begingroup$ @Travis Service: So we have the following situation. We can solve these two subproblems but at the same time we can't. What's the difference between solving in the first and the second cases? $\endgroup$
    – Oleksandr Bondarenko
    Dec 22, 2010 at 20:02
  • $\begingroup$ @Oleksandr: What happens if you run the P time algorithm of one subproblem on an instance of another subproblem? How do you interpret the results? $\endgroup$
    – Aryabhata
    Dec 22, 2010 at 20:13

3 Answers 3

Reset to default
11
$\begingroup$

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.

Suppose you are just asking for the answer, as in (b). Then you can partition the set of instances of $\Pi$ into "yes" instances and "no" instances. For each set of instances, there is a one-line program which gives you the answer for that set of instances. So in this case, the answer to your question is "yes."

Now, suppose, as in (a), you require a witness in the "yes" cases as well as the answer. Let the algorithms for the different subclasses be $A_1$, $A_2$, $A_3$, $\ldots$, $A_k$. Now we give a master algorithm $A$ that, given an instance $x$, runs all $k$ algorithms on it. $A$ checks the witnesses that the algorithms $A_i$ output to see whether one of them verifies that $x$ is a "yes" instances. If one of them does, then $A$ outputs "yes". Otherwise, $A$ outputs "no".

If $x$ is a "yes" instance, one of the algorithms $A_i$ must output a valid witness, and so $A$ will accept. If $x$ is a "no" instance, there are no valid witnesses, and so $A$ will reject. Thus, for case (a), if the answer to your question is "yes", $A$ solves an NP-complete problem in polynomial time, and we have P$=$NP.

None of this argument is original; I'm just consolidating and summarizing the answers that this question got on cstheory.

$\endgroup$
7
  • $\begingroup$ @Peter Shor: Indeed, the first paragraph of your answer is the one I wanted. Thank you very much! I think I'll post the link here on cstheory. $\endgroup$
    – Oleksandr Bondarenko
    Dec 23, 2010 at 1:25
  • $\begingroup$ @Peter Shor: It seems to me that you make different assumptions in the abobe-mentioned two cases: in case (a) you assume that the input for "one-line program" is from corresponding subproblem, but in case (b) you assume that $A$ doesn't know what subproblem given input belongs to. Do I correctly understand you answer? $\endgroup$
    – Oleksandr Bondarenko
    Dec 23, 2010 at 4:46
  • 1
    $\begingroup$ That's correct. This is because, in case (b), we're proving that if you can partition $\Pi$ into a finite number of polynomial-solvable subsets, then there's an algorithm $A$ which can solve NP-complete problems. Because we're trying to prove that $A$ can solve an arbitrary instance of $\Pi$, we can't assume that $A$ knows which subproblem a given input belongs to. $\endgroup$
    – Peter Shor
    Dec 23, 2010 at 13:04
  • $\begingroup$ @Peter Shor: Can we add to the case (b, yes/no instances) that the answer is "yes" if an algorithm knows to what class an input belongs to and "no" if it doesn't? If we can add this condition, then the case (a) is redundant and the key to the answer on my question lies in whether an algorithm knows that it can solve the input or not. Am I right with such conclusions? $\endgroup$
    – Oleksandr Bondarenko
    Dec 24, 2010 at 2:14
  • $\begingroup$ @Oleksandr, I can't quite parse what you're saying. $\endgroup$
    – Peter Shor
    Dec 24, 2010 at 2:23
3
$\begingroup$

If you allow exponentially many machines and each can know its serial number, try this. For travelling salesman, you have n! machines. Each one attempts to verify the cost of a trip for a given permutation, generated in a reasonable way from its serial number. This can be done in polynomial time. Each machine raises a bit if it succeeds. Can't you then combine these in log(n!) time, which is polynomial. You are still doing exponentially much computation, but spreading it over many machines.

$\endgroup$
3
  • $\begingroup$ So what's the answer on my question? $\endgroup$
    – Oleksandr Bondarenko
    Dec 22, 2010 at 23:52
  • 1
    $\begingroup$ So I would claim you can find and recognize the solution if you have that many machines. Each one has to turn its serial number into a permutation of n items, which takes basically n divisions and lookups (maybe each of order n), then just add up the path and check the sum against the limit. Report success or failure. Then you can or the results in log n! operations, still polynomial. And to find the correct one, you follow the tree backwards. If NP != P, you must have exponentially many machines. $\endgroup$
    – Ross Millikan
    Dec 23, 2010 at 2:18
  • $\begingroup$ Thank you for the explanation! $\endgroup$
    – Oleksandr Bondarenko
    Dec 23, 2010 at 4:37
1
$\begingroup$

The question is what do you exactly mean by "solving a partition" of a problem.

In Peter's answer on cstheory, the question is interpreted as "given an instance from the partition output the answer on that instance".

In Sadeq's answer, the question is interpreted as "given an instance, output the answer on that instance if it is in the partition, otherwise reject", if the problem is a decision problem, this becomes "decide the partition".

In short Peter is interpreting the question as a promise problem while Sadeq is interpreting it as deciding the partitions.

If you decide the partitions, you can combine them with OR to obtain the answer. However if you are deciding the promise version you cannot do this because the answer of each machine on instances that do not belong to that partition is not defined, so taking OR will not work.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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