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