<p>Underlying motivation for the question: if someone showed that <span class="math-container">$\text{P}=\text{NP}$</span> but the algorithm thus produced for, e.g., <span class="math-container">$3\text{-SAT}$</span>, runs in time <span class="math-container">$\Omega(n^G)$</span> where <span class="math-container">$G$</span> is <a href="https://en.wikipedia.org/wiki/Graham%27s_number" rel="nofollow noreferrer">Graham's number</a>, this would have no practical consequences whatsoever -- because <span class="math-container">$G$</span> is so large that it can't even be written down other than as a computation, so that already for <span class="math-container">$n=2$</span> an algorithm that uses that many steps is 'fiction'.</p>
<p>On the flip-side, if the exponent proved to be, say, <span class="math-container">$2$</span>, that would turn everything upside down. That world would be truly bizarre.</p>
<p>Surely it must be known that the exponent must be <span class="math-container">$&gt;2$</span>. But what is in fact known?</p>

CC BY-SA 4.0
2021-01-06T14:23:19.913Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-01-06T14:33:33.813Z
If P = NP constructively, that gives some reduction algorithm. Its complexity might depend on a number of things, but one would still expect the result to map to $O(n^{d + \ldots})$ for some $d$, with ... being the things that vary. That $d$.
Jacques Carette
CC BY-SA 4.0
2021-01-06T16:20:25.717Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2021-01-06T17:53:15.173Z
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](https://www.math.ucsd.edu/~sbuss/ResearchWeb/npProofLimits/paper-journal.pdf).
William Hoza
CC BY-SA 4.0
2021-01-06T19:00:42.957Z
Rather than downvoting me, can someone help me phrase the question that I should be asking instead? There has to be a way to quantify the intuition that "even in P = NP, in practice, it won't make any difference at all, because X". The question above was my attempt at quantification. It failed. What's a better way to ask?
Jacques Carette
CC BY-SA 4.0
2021-01-06T20:25:42.980Z
@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.
William Hoza
CC BY-SA 4.0
2021-01-06T23:01:05.560Z
@WilliamHoza I agree! I guess I'm surprised that 1.8019 is the best that can be done.
Jacques Carette
CC BY-SA 4.0
2021-01-16T18:57:21.867Z
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.
Ryan Williams
<cc.complexity-theory><time-complexity><lower-bounds>
Is there a known lower-bound on what the exponent could be, even if it turned out that P=NP?
Jacques Carette
# Is there a known lower-bound on what the exponent could be, even if it turned out that P=NP?

(Asked by: username_0 on 2021-01-06)

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](https://en.wikipedia.org/wiki/Graham%27s_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?

**Tags:** cc.complexity-theory, time-complexity, lower-bounds

> **Comments:**
> **username_1**: 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.  
> **username_0**: If P = NP constructively, that gives some reduction algorithm. Its complexity might depend on a number of things, but one would still expect the result to map to $O(n^{d + \ldots})$ for some $d$, with ... being the things that vary. That $d$.  
> **username_1**: 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$.  
> **username_2**: 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](https://www.math.ucsd.edu/~sbuss/ResearchWeb/npProofLimits/paper-journal.pdf).  
> **username_0**: Rather than downvoting me, can someone help me phrase the question that I should be asking instead? There has to be a way to quantify the intuition that "even in P = NP, in practice, it won't make any difference at all, because X". The question above was my attempt at quantification. It failed. What's a better way to ask?  
> **username_2**: @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.  
> **username_0**: @WilliamHoza I agree! I guess I'm surprised that 1.8019 is the best that can be done.  
> **username_3**: 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.  

---

## 0 answers

