[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: NP-complete problems solved?
>>>>> "STW" == Sai To Wang <swang@xxxxxxxxxxxxxxxxx> writes:
>> -----Mensaje original----- De: Patrick G. Bridges
>> [mailto:bridges@xxxxxxxxxxxxxxxxx] Enviado el: lunes 23 de octubre
>> de 2000 12:30 Para: computer-go@xxxxxxxxxxxxxxxxx Asunto: Re:
>> computer-go: NP-complete problems solved?
>>
>> Go is *not* NP, Go is PSPACE-complete, and PSPACE > NP.
>>
STW> As far as I know, GO si PSPACE-complete without Ko and is
STW> EXPTIME with Ko.
Ah. :) In that case, P = NP doesn't help since, as someone stated, P
is a strict subset of EXPTIME.
--
*** Patrick G. Bridges bridges@xxxxxxxxxxxxxxxxx ***
*** #include <std/disclaimer.h> ***