The proof someday that P is not equal to NP could be a very disappointing or unsatisfying proof: a single problem, perhaps a very weird "silly" problem in NP with no practical significance, might be proved as not solvable in P.
For example, hypothetically, "Fermat numbers with indices greater than 2^1000000 cannot be factored in time polynomial in the length of their (rather boring) binary representation." (Numbers the size of a Fermat number with an index larger than about 30 are practically useless for RSA cryptography.)
Previously, speculating the dual: things could remain interesting even if P=NP.
No comments :
Post a Comment