According to Dr. Ericsson, you can do anything you put your mind to.

]]>As Greg Kuperberg mentioned, the proof that Go is EXPTIME hard uses the facts that EXPTIME = alternating poly space and that Go’s ko rule forbids cycles of length 2.

Interestingly enough, even simple things (on a 19×19 Go board) get hard on a nxn Go board:

http://homepages.cwi.nl/~tromp/lad.ps

What complexity class is this? It is equivalent to make Arthur a finite-state automaton with exponentially many states?

I would suppose so. If so, then I suppose that it probably is EXPSPACE.

The question remains why chess is easier than this.

]]>This is why it is not known if Go under Chinese or American rules is in EXPTIME, although it is clearly in EXPSPACE.

]]>> it is in EXPSPACE. It is not clear to me

> at the moment why it is actually in

> EXPTIME.

Greg, I think the reason is that each position can be described in polynomial space, so the problem is in Alternating Polynomial Space (APSPACE, is that class in the zoo?), which is equal to EXPTIME.

]]>