0
$\begingroup$

I'm not sure how lower bounds affect the question to the P=NP problem.
I.e. :
Let a SAT instance with a size of n be transformed into an instance of a problem X with a size of n3.

If you find a lower bound of the SAT problem which is $$\Omega(c^n) \ \ \ \ c > 1 $$

What would be the consequence to the problem P=NP?

We already know that SAT has an at exponential lower bound time complexity. But what would be the complexity of the problem X? Will it be $$\Omega((c^n)^3)$$

Will X's complexity affect the problem N=NP in any way? (assuming that the lower bound for SAT exists).

My thought are that since SAT is NP-complete there should be no problem in having an exponential lower bound. Any thoughts?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ "We already know that SAT has an at exponential lower bound time complexity". No we don't, that's the whole point of the P vs NP problem. $\endgroup$ – jmite Dec 8 '17 at 18:43
  • $\begingroup$ So if SAT has an exponential lower bound it means that it's definitely not in P. But SAT is in NP. So there are problems in NP which are not in P, meaning P is not equal to NP? $\endgroup$ – Billy Joel Dec 8 '17 at 20:14
  • 1
    $\begingroup$ Exactly. If SAT has an exponential (or even super polynomial) lower bound then $P \neq NP$, and if it has a polynomial upper bound then $P=NP$ $\endgroup$ – jmite Dec 8 '17 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.