The Cook-Levin theorem shows that any NP problem is reducible to an NP-complete problem.

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

But If an NP problem is shown to have an exponential lower bound, would that prove that P != NP?

  • $\begingroup$ Please do your own homework. $\endgroup$ – Yuval Filmus Oct 28 '17 at 20:22
  • $\begingroup$ @YuvalFilmus i think now it's better $\endgroup$ – Nick Oct 29 '17 at 0:58
  • $\begingroup$ Indeed so. The answer to your updated question is within your capabilities. Use the definition of set equality. $\endgroup$ – Yuval Filmus Oct 29 '17 at 6:18
  • $\begingroup$ Hint: Look for the definition of NP-hardness. $\endgroup$ – clemens Oct 29 '17 at 8:26
  • $\begingroup$ You mean a non-polynomial lower bound for (infinitely many instances of) some NP problem. By definition of NP-complete it will lift to any NP-complete problem. $\endgroup$ – reuns Oct 29 '17 at 10:18