1
$\begingroup$

Two things (this may be naive):

  1. Does anyone believe there is a sub-exponential time algorithm for the Subset-sum problem? It seems obvious to me that you would have to look through all possible subsets to prove (the negation of) an existential statement. It seems obvious in the same way that if somebody asked you "Is $x$ in this list of $n$ numbers?", it's obvious that you would have to look through all $n$ numbers.

  2. If Subset-sum can be polynomial time reduced to 3SAT and we agree on (1), then doesn't that mean $NP \neq P$?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ I don't think it's fair to use 'obvious-ness' as a metric. Hall's condition requires that $\forall S' \subseteq S, |N(S')| \geq |S'|$ for a system of distinct representatives. Yet we can do a matching in polynomial time! $\endgroup$ – Nicholas Mancuso Apr 7 '12 at 21:51
  • 1
    $\begingroup$ 'It seems obvious in the same way that if somebody asked you "Is x in this list of n numbers?", it's obvious that you would have to look through all n numbers.' That depends on your definition of "list". If we use Java's definition (i.e. any datastructure that supports the operations defined in the List interface), it's definitely possible to define a list data structure for which membership is an $O(log n)$ operation. $\endgroup$ – sepp2k Apr 7 '12 at 21:57
  • 4
    $\begingroup$ This question is borderline-cranky. Please clarify what you are asking beyond "Why is not trivially P $\neq$ NP?". $\endgroup$ – Raphael♦ Apr 7 '12 at 22:13
  • 2
    $\begingroup$ Why even talk about 3SAT? SUBSET-SUM is in NP and the non-existence of a sub-exponential algorithm for SUBSET-SUM is good enough to prove $P \neq NP$. You don't even need 2) or take examples of problems which are NP-Complete. $\endgroup$ – Aryabhata Apr 8 '12 at 4:17
  • 1
    $\begingroup$ "Does anyone believe there is a sub-exponential time algorithm for the Subset-sum problem?" I believe there could be... and so should everybody else, until there is a correct proof to the contrary. $\endgroup$ – Patrick87 Apr 8 '12 at 4:49
6
$\begingroup$

There is an algorithm for subset-sum that runs faster than $O(2^n)$! That is, it is faster than examining all possible subsets. This proves that your intuition is wrong. Wikipedia has a nice writeup of this algorithm.

If Subset-sum can be polynomial time reduced to 3SAT and we agree on (1), then doesn't that mean $NP \neq P$?

If someone proves (1) (the above algorithm is still exponential), then yes, $P \neq NP$. However, if all humans on earth would somehow 'agree' that (1) is true, then that is not enough to make $P \neq NP$ proven - just to address your specific usage of the word 'agree'.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I didn't say agreement magically overrules an absence of a proof. Thanks for the addressing that though. $\endgroup$ – anonymous Apr 7 '12 at 22:38
3
$\begingroup$

Does anyone believe there is a sub-exponential time algorithm for subset-sum?

I'm sure there's someone somewhere who believes it, but the vast majority of computer scientists believe that there is no such algorithm. However no one has proved this yet.

It seems obvious to me that you would have to look through all possible subsets to prove the negation of an existential statement.

This is not generally true. There are a lot of problems of the form "Does there exist a subset of a given set for which some property is true" that can be solved without looking at all subsets.

If subset-sum can be polynomial time reduced to 3SAT and we agree on (1), then doesn't that mean NP =/= P?

Yes, if someone proves that it is not possible to solve subset-sum in polynomial time, that also proves that $NP \neq P$.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

It is a bit strange that you are talking about reducing SUBSET-SUM to 3SAT to conclude $P \neq NP$ from the hypothesis of non-existence of a sub-exponential algorithm for SUBSET-SUM.

The fact that SUBSET-SUM is in $NP$, coupled with the hypothesis that it has no polynomial time algorithms is enough to show that $P \neq NP$. There is no need to talk about any reductions, or even pick problems which are $NP$-Complete.

So let us try to re-interpret your problem to what I think you might be asking:

Suppose problem $A$ can be reduced to problem $B$ in polynomial time. Does the non-existence of a sub-exponential time algorithm ( $o(c^n)$ for every $c \gt 1$, note: smallOh) for $A$ imply the non-existence of a sub-exponential time algorithm for $B$?

The answer is not necessarily.

This is because the polynomial time algorithm for reduction can blow up the size of your input!

Suppose every reduction from $A$ to $B$ changed the input size from $n$ to $n^3$.

Now any $\Theta(2^{\sqrt{k}})$ time algorithm for $B$ (with input size $k$) will solve $A$ (with input size $n$) in $\Theta(2^{n^{3/2}})$ time, and does not contradict the non-existence of a sub-exponential time algorithm for $A$.

See also this question on cstheory.SE.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ "sub-exponential time algorithm (say $o(2^n)$)" -- but $o(2^n)$ is not subexponential! Take $1.5^n \in o(2^n)$, for instance. The rest of your reasoning is somewhat valid (i.e. that the reduction can cause higher complexity) but you use the term "sub-exponential" in the wrong way. $\endgroup$ – Raphael♦ Apr 8 '12 at 9:23
  • $\begingroup$ @Raphael: That was just a specific example, choosing a specific constant for the base. I would not have used the word "say" otherwise. I was in no way claiming that $1.5^n$ is not exponential. You are right though, it could be interpreted the way you did, so I have edited it. Thanks. $\endgroup$ – Aryabhata Apr 8 '12 at 14:59
  • $\begingroup$ Ok. Only now the last paragraph is off; if you wanted to justify your "NO!" you would have to give a (truly) subexponentially solvable problem; in particular, the polynomial time reduction would have to output an exponentially-sized output. I don't see that line of reasoning working out. $\endgroup$ – Raphael♦ Apr 8 '12 at 15:32
  • $\begingroup$ @Raphael: Where are you getting "exponential sized output" from? $2^{\sqrt{n}}$ is truly sub-exponential (i.e. $o(c^n)$ for any $c \gt 1$), and so a quadratic blowup is enough. Of course, I don't have a concrete example, as proving that every reduction would result in a quadratic blowup is probably too difficult (and I am not aware of any off hand). $\endgroup$ – Aryabhata Apr 8 '12 at 16:10
  • $\begingroup$ Huh, I thought $2^\sqrt{n}$ was exponential. Never mind, then. Although WA (fix ^) seems to disagree; bug or numerical artifact? $\endgroup$ – Raphael♦ Apr 8 '12 at 16:21

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.