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.

  • 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.2010-12-22
  • 0
    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.2010-12-22
  • 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.2010-12-22
  • 0
    @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?2010-12-22
  • 0
    @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?2010-12-22
  • 0
    @Moron: It rejects or fails to halt.2010-12-22
  • 0
    @Oleksandr: That is an additional assumption you are making!2010-12-22
  • 0
    @Moron: You mean additional essential assumption?2010-12-22
  • 0
    @Olek: I was talking about your statement of finite subproblems -> just run algorithm for each and hence in P... That requires additional assumptions.2010-12-22
  • 0
    @Moron: What kind of additional assumptions, maybe, some example, or direction of search?2010-12-22
  • 0
    @Olek: I have no clue what you are talking about! Consider the 3SAT example Travis gave. Given an input, you subproblem algorithms will give YES and NO. Now how do you interpret the results of these?2010-12-22
  • 0
    @Moron: I interpret this as the case where we solve these subproblems of 3SAT when we know what class an instance belongs to. If we don't know what class an instance belongs to we can't solve them in P unless P=NP.2010-12-22
  • 0
    @ShyPerson: Not at all. I asked about partition of the set of input graphs not some input graph.2010-12-22
  • 0
    @OLek: So you seem to agree with the first comment Qiaochu made...2010-12-22
  • 0
    @Moron: Yes, I agree. But I'm confused with such comment from cstheory concerning non-recognizability: Oleksandr, no, that’s not a problem. Let $p_1,\dots,p_n$ be polynomial upper bounds to the running time of $M_1,\dots,M_n$ respectively. On input $x$, the machine $M$ can just run all machines $M_1,\dots,M_n$ for up to $max\{p_1(|x|),…,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 at 23:062010-12-22
  • 0
    @Olek: Antonio's comment assumes that we actually are able to decide which subproblem it is! If for a certain subset of input, only $M_1$ accepts and rest of them reject, then we have an algorithm to decide the subproblem...2010-12-22
  • 0
    @Moron: As I understood from the discussion the answer on my question is yes if we neglect recognition and no if all the subproblems are polynomially recognizable?2010-12-22

3 Answers 3

10

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.

  • 0
    @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.2010-12-23
  • 0
    @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?2010-12-23
  • 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.2010-12-23
  • 0
    @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?2010-12-24
  • 0
    @Oleksandr, I can't quite parse what you're saying.2010-12-24
  • 0
    @Peter Shor: I mean that it doesn't matter whether we require witness or not. What matters is whether we allow algorithms know what part of partition an input is from. And I ask is this reasoning correct?2010-12-24
  • 0
    @Oleksandr: In the case (b), the algorithm can use the witness to find out which part of the partition the input belongs to (at least in the case of "yes" instances).2010-12-24
4

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.

  • 0
    So what's the answer on my question?2010-12-22
  • 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.2010-12-23
  • 0
    Thank you for the explanation!2010-12-23
1

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.