# Is there a known lower-bound on what the exponent could be, even if it turned out that P=NP?

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?

• 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. Jan 6 '21 at 14:23
• 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$. Jan 6 '21 at 16:20
• 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. Jan 6 '21 at 17:53
• @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. Jan 6 '21 at 20:25
• 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. Jan 16 '21 at 18:57