[4666] in Central_America
Re: New quotes for Thu Nov 19
pshuang@ATHENA.MIT.EDU (pshuang@ATHENA.MIT.EDU)
Fri Nov 20 18:18:00 1992
NP problems are those which are hard to solve, and I think the criterion
Andy gave, O_sub_t(polynomial) is correct. I believe most NP problems
have been shown to be isomorphic to just a handful (don't remember how
many, may be just one but I don't think so). The significance, should
someone have successfully proved the NP set of problems are all actually
P, are two-fold: (a) many theoretical mathematicians will just hang up
their hats and quit, but many more will run with the proof and see what
it leads to, with lots of comcomitant excitement, which one doesn't
often see in mathematics; (b) some techniques, notably certain forms of
encryption, are "dependent" on being NP problems to remain secure.
