Two things (this may be naive): Does anyone believe there is a sub-exponential t
ID: 646561 • Letter: T
Question
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?P?
Explanation / Answer
There is an algorithm for subset-sum that runs faster than O(2n)! 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?P?
If someone proves (1) (the above algorithm is still exponential), then yes, P?NP. However, if all humans on earth would somehow 'agree' that (1) is true, then that is not enough to make P?NP proven - just to address your specific usage of the word 'agree'.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.