Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Qiaochu Yuan Dec 22 '10 at 19:09
    
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. –  Oleksandr Bondarenko Dec 22 '10 at 19:13
1  
@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. –  Travis Service Dec 22 '10 at 19:42
    
@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? –  Oleksandr Bondarenko Dec 22 '10 at 20:02
    
@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? –  Aryabhata Dec 22 '10 at 20:13
show 12 more comments

3 Answers

up vote 10 down vote accepted

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.

share|improve this answer
    
@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. –  Oleksandr Bondarenko Dec 23 '10 at 1:25
    
@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? –  Oleksandr Bondarenko Dec 23 '10 at 4:46
1  
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. –  Peter Shor Dec 23 '10 at 13:04
    
@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? –  Oleksandr Bondarenko Dec 24 '10 at 2:14
    
@Oleksandr, I can't quite parse what you're saying. –  Peter Shor Dec 24 '10 at 2:23
show 2 more comments

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.

share|improve this answer
    
So what's the answer on my question? –  Oleksandr Bondarenko Dec 22 '10 at 23:52
1  
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. –  Ross Millikan Dec 23 '10 at 2:18
    
Thank you for the explanation! –  Oleksandr Bondarenko Dec 23 '10 at 4:37
add comment

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.

share|improve this answer
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.