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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s