# Subset-sum and 3SAT

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$?

• 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! Apr 7 '12 at 21:51
• '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. Apr 7 '12 at 21:57
• This question is borderline-cranky. Please clarify what you are asking beyond "Why is not trivially P $\neq$ NP?".
– Raphael
Apr 7 '12 at 22:13
• 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. Apr 8 '12 at 4:17
• "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. Apr 8 '12 at 4:49

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

• I didn't say agreement magically overrules an absence of a proof. Thanks for the addressing that though. Apr 7 '12 at 22:38

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

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$?

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

• "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.
• @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. Apr 8 '12 at 14:59
• @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). Apr 8 '12 at 16:10
• Huh, I thought $2^\sqrt{n}$ was exponential. Never mind, then. Although WA (fix ^) seems to disagree; bug or numerical artifact?