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?


closed as unclear what you're asking by fade2black, Shaull, Yuval Filmus, Juho, Evil Oct 29 '17 at 0:17

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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