We’d like to know whether P = NP or not. In other words, we want to be able to simulate non determinism with determinism. What’s the easiest thing we can do ? we can try “all guesses”: roughly, this leads to a bound of the form \displaystyle {c(M)^{t(n)}} if t(n) is the running time of the nondeterministic machine.

Dick Lipton has a proof on his blog of a much stronger result of the form
{c^{t(n)}}, where c is INDEPENDENT of the nondeterministic machine.

He also has a general conjecture that might be provable:

For any \epsilon > 0,
NTIME(f(n)) \subseteq TIME(2^{\epsilon f(n)})

in other words, maybe it’s exponentially faster, but in a tiny way. I encourage you to read the post, understand the theorem, and think about this conjecture. Note that proving the conjecture doesn’t lead to anything earth shattering, but it would be a neat result to have.

Advertisements