computer-go: Hardness of Go

[Timo Puha <eleinion@xxxxxxxxx>]

On Mon, 2 Oct 2000, TMCooper wrote:

> > This is one occasion when it is useful to call on the theoretical result,
> > that Go is NP complete.  Therefore there cannot be this sort of hidden
> > secret, valid on boards of all sizes, depending only on computation linear
> > in the board size.
> 
> Do you know a reference for this result?   Thanks.  Tom.

Actually Go is quite a bit harder than NP-complete. I know of two papers
concerning this and here is the BiBTeX info on them:

@Article{LichtensteinS80,
title={{GO} is Polynomial-Space Hard},
author={David Lichtenstein and Michael Sipser},
area={Theory of Computation},
pages={393--401},
journal=jacm,
month=apr,
year=1980,
volume=27,
number=2,
keywords={},
cr64-categories={},
source={http://theory.lcs.mit.edu/~jacm/jacm.bib}
}

@InProceedings{Robson1983,
  author =       "J. Robson",
  title =        "The Complexity of Go",
  booktitle =    "Proc. IFIP (International Federation of Information
                 Processing)",
  editor =       "R. E. A. Mason",
  publisher =    "North Holland",
  pages =        "413--417",
  year =         "1983",
}

-Timo Puha