[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>		       ***