# P versus NP and lower bounds for SAT

Despite numerous attempts, the P versus NP problem remains unsolved after 40 years. It is arguably the biggest open problem in theoretical computer science and even in all of mathematics. Most people believe that $P \neq NP$, which would imply that there exist problems in $NP$ that require superpolynomial time (but this would leave open the possibility that all problems in $NP$ can be solved in subexponential time!). The exponential time hypothesis, a claim stronger than $P\neq NP$, would imply that there exist problems in $NP$ that cannot be solved in subexponential time.

Even though most believe that $P\neq NP$ (as evidenced by this poll of theorists), I’m relatively shocked at how little is known about lower bounds on running time. As noted by David Juedes:

I think we need to build techniques to prove general purpose lower bounds, before we can get to the P vs NP question. For example, I do not believe that anyone has shown that Vertex Cover requires $O(n^3)$[sic] steps on a Turing machine. If we can’t do that, how can we expect to prove that P is not equal to NP?

Ryan Williams notes that the best known lower bound for SAT is just as dismal:

As far as I know, the best known “model-independent” time lower bound for SAT is the following. Let $T$ and $S$ be the running time and space bound of any SAT algorithm. Then we must have $T S \geq n^{c-{o(1)}}$ infinitely often,

where $c=2 \cos (\frac{\pi}{7})\approx 1.801$.