1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ By definition, $P \subseteq NP$. So no. $\endgroup$ – Pseudonym Aug 20 '15 at 2:05
  • 1
    $\begingroup$ it means that no NP-hard problems can be solved in P time. NP-hard problems are the set NP - P. see also NPI the class of NP-hard problems "between" P and NP complete. $\endgroup$ – vzn Aug 20 '15 at 4:17
  • 2
    $\begingroup$ @vzn "it means that no NP-hard problems can be solved in P time." Correct. "NP-hard problems are the set NP - P." False: the halting problem is NP-hard but is not in NP-P. We don't even know that NP-complete = NP - P. $\endgroup$ – David Richerby Aug 20 '15 at 7:31
  • 1
    $\begingroup$ Nitpick: "non-polynomial" != ”exponential" $\endgroup$ – Raphael Aug 20 '15 at 15:03
  • 1
    $\begingroup$ @DavidRicherby Note that it is impossible for (NP-complete = NP-P). We know the LHS has at least one language, so if the equation held then P != NP, and so by Ladner's theorem there would be at least one language in NP-P that is not NP complete. So we actually do know this equation is false. $\endgroup$ – Ryan Williams Aug 22 '15 at 20:02
5
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ "However, there will be some other NP problems (which aren't NP-complete) that can be solved in polynomial time." For example, all of P! $\endgroup$ – David Richerby Aug 20 '15 at 7:33
  • 1
    $\begingroup$ One thing to stress: we don't need any theorem for the conclusion, just the definitions, a P problem and the assumed lower bound. $\endgroup$ – Raphael Aug 20 '15 at 15:05
1
$\begingroup$

Just to add the simple counter example, even if $P \neq NP$, we still have $P \subset NP$, so every problem in $P$ is also an $NP$-problem, and can be, by definition, solved in polynomial time.

$\endgroup$

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.