[4667] in Central_America
Re: New quotes for Thu Nov 19
eichin@CYGNUS.COM (eichin@CYGNUS.COM)
Fri Nov 20 18:59:02 1992
The handful of problems are known as "NP-complete", and if any
NP-complete problem can be solved in P time, then *all* NP problems
can (usually shown be converting problems to each other...)
Factoring of integers is NP; it may be NP-complete but I'm not
sure if that has been proven. If factoring can be reduced to P, that
should imply faster factoring algorithms, and a practical blow to the
strength of RSA; it also opens up some interesting research, and
there are other classic theorems that could either be proven or
disproven.
One of the authors of the Graph Isomorphism paper has
apparently been hacking on the P=NP problem for years...
