Problem Detail: I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it will mean that all problems in NP can be solved in polynomial time. My question is: does this proof also hold the other way? I.e. if an exponential lower bound for an NP-complete problem is proved, would that mean that no problems in NP can be solved in polynomial time?
Asked By : haydnv
Answered By : D.W.
Not quite. If there’s an exponential lower bound for a NP-complete problem, then it follows that no NP-complete problem can be solved in polynomial time. However, there will be some other NP problems (which aren’t NP-complete) that can be solved in polynomial time. If there’s an exponential lower bound for any NP problem, then it follows that P != NP. In particular, an exponential lower bound for some problem means that the problem is not in P. So, if you have an exponential lower bound for some NP problem, that means the problem is in NP but not in P — which means NP contains a problem that is not in P — which means that NP != P. It might help to recall that NP is a set of problems (the set of all search problems where YES answers have a polynomial-size witness that can be verified in polynomial time). Similarly, P is a set of problems (the set of all search problems that can be solved in polynomial time). So, if you’ve found one element of NP that is not an element of P, you can immediately conclude that those two sets are not the same sets. Or, to put it another way: your second paragraph is the contrapositive of the statement in the first paragraph. If there is a NP problem with a non-polynomial lower bound, then not every problem in NP can be solved in polynomial time. If not every problem in NP can be solved in polynomial time, then it follows that no polynomial-time algorithm can be found for any NP-complete problem. See What is the definition of P, NP, NP-complete and NP-hard? for more background.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/45417