> If P=NP, go is a P problem. But what is the "n" used for the determination of > complexity ? is it the size of the board ? if the exposant of n is a huge > number (and it might be), then this doesn't help a lot... Except according to a proof in Papadimitrou;s "Computational Complexity", Go is *not* NP, Go is PSPACE-complete, and PSPACE > NP.