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 , which would imply that there exist problems in that require superpolynomial time (but this would leave open the possibility that all problems in can be solved in subexponential time!). The exponential time hypothesis, a claim stronger than , would imply that there exist problems in that cannot be solved in subexponential time.

Even though most believe that (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 [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 and be the running time and space bound of any SAT algorithm. Then we must have infinitely often,

where .

### Like this:

Like Loading...

*Related*