Douglas_Knight comments on The Curve of Capability - Less Wrong

18 Post author: rwallace 04 November 2010 08:22PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (264)

You are viewing a single comment's thread. Show more comments above.

Comment author: Douglas_Knight 07 November 2010 03:52:50AM 1 point [-]

There are many fairly natural problems which are not in P. For example, given a specific Go position does white or black have a win? This is in EXP

Are you saying that evaluating a Go position has exponential (time?) cost even on a nondeterministic machine?

If one assumes everything that is conjectured, then yes. To say that it is EXP-hard is to say that it takes exponential time on a deterministic machine. This does not immediately say how much time it takes on a non-deterministic machine. It is not ruled out that NP=EXP, but it is extremely implausible. Also doubted, though more plausible, is that PSPACE=EXP. PSPACE doesn't care about determinism.