Underlying motivation for the question: if someone showed that $\text{P}=\text{NP}$ but the algorithm thus produced for, e.g., $3\text{-SAT}$, runs in time $\Omega(n^G)$ where $G$ is Graham's number, this would have no practical consequences whatsoever -- because $G$ is so large that it can't even be written down other than as a computation, so that already for $n=2$ an algorithm that uses that many steps is 'fiction'.

On the flip-side, if the exponent proved to be, say, $2$, that would turn everything upside down. That world would be truly bizarre.

Surely it must be known that the exponent must be $>2$. But what is in fact known?

  • 12
    $\begingroup$ The exponent of what exactly? Even unconditionally, for every $c$ there is a language in P (and thus NP) that’s not computable in time $O(n^c)$. On the other hand, there are no known superlinear lower bounds on, say, SAT. $\endgroup$ Jan 6, 2021 at 14:23
  • 6
    $\begingroup$ But algorithm for what language? NP is not a single language, but a class of languages. Different NP languages will have different complexity with different exponents $d$. $\endgroup$ Jan 6, 2021 at 16:20
  • 6
    $\begingroup$ It's known that any algorithm for SAT that uses $n^{o(1)}$ space must use at least $n^{1.8019}$ time. I think that's the closest known result to what you're asking for. See e.g. this paper. $\endgroup$ Jan 6, 2021 at 17:53
  • 6
    $\begingroup$ @JacquesCarette, if someone could prove unconditionally that "SAT requires at least $n^{100}$ time," I think that statement would be a good value of X. Unfortunately, nobody knows how to prove that statement or anything even close. If we are being honest, we must admit that it is a genuine possibility that there are fast, practical algorithms for SAT and other important NP-hard problems. $\endgroup$ Jan 6, 2021 at 20:25
  • 3
    $\begingroup$ If you require the SAT algorithm to print a satisfying assignment when one exists, the time lower bound (in the case of n^(o(1)) space) can be improved to about n^2. See McKay and Williams ITCS 2019. In fact such a lower bound is known for much easier problems in P dating back to Beame 1989 at least. $\endgroup$ Jan 16, 2021 at 18:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.