[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: computer-go: NP-complete problems solved?



-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



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

As far as I know, GO si PSPACE-complete without Ko and 
is EXPTIME with Ko.


Wang Sai To
[wangsaito@xxxxxxxxxxxxxxxxx]

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.5.1 for non-commercial use <http://www.pgp.com>

iQA/AwUBOfWUzuZY4pnmQAOVEQJY+QCg05WSF0d9zeeyoD8fB/4QMnOmL48AoOgg
jxmq9GUHU5yxrA6kDPDpeYUH
=ODVr
-----END PGP SIGNATURE-----