[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
> Now, it turns out that if P = NP, then P = NP = PSPACE, and
I never heard that, where can I found more information about this claim.
> Go should be
> soluble in polynomial time. Of course, most people believe
> that P != NP, and
> that PSPACE is a strict superset of P and NP, but no one has
> proved it yet.
> The person we're talking about claims to have proven that P =
> NP by solving
> a known NP-complete problem, the k-clique problem.
>
> -Patrick
>
Thanks
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.5.1 for non-commercial use <http://www.pgp.com>
iQA/AwUBOfWUKOZY4pnmQAOVEQJ5uQCeKCCTtUa8t4kjP9syqZ38gEocaxUAoIkf
5OHUbgtMDO3Lt+RkQEb6DVRj
=JUb9
-----END PGP SIGNATURE-----