Re: computer-go: Hardness of Go

["Charles Matthews" <charles@xxxxxxxxxxxxxxxxxx>]

-----Original Message-----
From: Timo Puha <eleinion@xxxxxxxxxxxxxxxxx>
To: computer-go@xxxxxxxxxxxxxxxxx <computer-go@xxxxxxxxxxxxxxxxx>
Date: 02 October 2000 15:02
Subject: computer-go: Hardness of Go


>
>
>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.

Yes, now I look in Garey and Johnson, Computers and Intractability, it's
PSPACE-hard.  So, what Nick Wedd is saying can be answered this way, unless
by some chance complexity theory collapses.  Of course this effectively
tells you nothing about 19x19 Go.

Charles