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 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

, where c is INDEPENDENT of the nondeterministic machine.

He also has a general conjecture that might be provable:

For any ,

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.

### Like this:

Like Loading...

*Related*

## 1 comment

Comments feed for this article

May 12, 2009 at 12:08 pm

rjliptonThanks for the comments…rjlipton

I do think that we can get somewhere on this type of result. I look forward to see what happens next.