 vpokoPremium
join:2003-07-03
Boston, MA
1 edit | said by DataRiker:said by vpoko: In math, provable has a very precise meaning.
The N=NP problem might not even be provable one way or the other. Read Godel's work on incompleteness if your curious. ( If remember correctly, Godel himself doubted that an equivalent problem had a solution as early the 1950's) Which brings up the reason for my last reply. knowing this, at what point would you feel comfortable saying the N=NP is false? Should we refrain from saying Mathematically secure forever? It's possible that P vs. NP is independent of a particular set of axioms (like ZF set theory), though I don't know of any convincing arguments for that being true. Interestingly enough, if it's independent, there may actually be a proof of its independence (such as the proofs of independence that exist for the axiom of choice and continuum hypothesis), or the proof may itself be independent (ad infinitum). It's also possible that only a non-constructive proof exists, for example showing that P=NP but without giving us an algorithm for solving an NP-complete problem like 3SAT. Both of those options would be incredibly unsatisfying. Scott Aaronson, currently a computer science professor at MIT specializing in computational complexity theory, wrote a great survey article on the possibility of formal independence for the P vs. NP problem. It that can be found here: »www.scottaaronson.com/papers/pnp.pdf.
As far as verbiage, yes, in the absence of a formal proof I would refrain from calling something mathematically proven. That's not to say that I wouldn't use the ciphers in practice, and even assume that they're probably secure, but math isn't like physics - in math, a formal proof is the only kind of proof. Incidentally, it's said that the legendary Richard Feynman refused to even accept P vs. NP as an open problem because it was so obvious that they were not equal. But after all, Richard Feynman was a physicist. |
