[computer-go] Complexity of Go

[Bob Hearn]

(Sorry if this is a duplicate; the first posting didn't show up.)

To clarify (or maybe not) the status of the computational complexity  
of NxN go:

Go with Japanese rules is EXPTIME-complete (Robson, 1983).

Go with superko is only known to be PSPACE-hard, and EXPSPACE-easy  
(Robson, 1984). That is, both the upper and the lower bounds in  
Robson's EXPTIME-completeness proof fail. It is rather surprising that  
neither of those bounds has been tightened in the ~25 years since the  
last relevant papers.

Slightly confusing the issue is a "proof" in Papadimitriou's book that  
go is PSPACE-complete (Papadimitriou, 1993). However, the problem he  
considers is actually a modification of go which prevents  
exponentially long games, thus putting the problem trivially in  
PSPACE. Unfortunately this proof has been cited by others in claims  
that go is PSPACE-complete.

But fascinating as these complexity issues are (I've spent a fair  
amount of time trying to prove that go with superko is EXPSPACE- 
complete), I don't think they are really relevant to computer go.

Bob Hearn



References:

J. M. Robson. The complexity of Go. In Proceedings of the IFIP 9th World
Computer Congress on Information Processing, pages 413–417, 1983.

J. M. Robson. Combinatorial games with exponential space complete  
decision
problems. In Proceedings of the Mathematical Foundations of Computer  
Science
1984, pages 498–506, London, UK, 1984. Springer-Verlag.

Christos H. Papadimitriou. Computational Complexity. Addison Wesley,  
1993.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/