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