Two things (this may be naive):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.If Subset-sum can be polynomial time reduced to 3SAT and we agree on (1), then doesn't that mean $NP \neq P$?
Subset-sum and 3SAT
complexity theory;time complexity;np complete;reductions