Replies

A decision problem is in PSPACE if there is a polynomial p(x) such that the problem can be solved by a Turing machine that is guaranteed to halt and that, when presented with an input of size x, requires the use of at most p(x) tape cells for the computation. [If you like, you can replace "Turing machine" with "computer", and "size x" or "x tape cells" with "x bytes". That yields an equivalent definition.]

A problem is PSPACE-complete if it's in PSPACE and if every problem in PSPACE can be reduced to it (via a computation bounded by polynomial time in the size of the input).

Asking whether a game like Go is in PSPACE isn't really an accurate phrasing, since the concept of PSPACE only applies to problems with arbitrarily large inputs. The conjecture is that Go played on an arbitrary-sized board is in PSPACE; the problem to be solved would be something like: given a Go position on any size board, determine whether it's a winning position for White or for Black (or if it's a tie -- I forget, does Go have drawn games?). If there is some halfway-reasonable limit (polynomial in the size of the board) on the number of moves in a game of Go, then Go is in PSPACE. I don't know if there is such a limit or not. (But even if not, it's solvable in exponential time, so it's still far short of universal Turing-machine complexity.)