tag:blogger.com,1999:blog-3722233.post109415958994837849..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Is Encryption Doomed?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-1094487977184205902004-09-06T11:26:00.000-05:002004-09-06T11:26:00.000-05:00That article is reporting the recent breaks of md4...That article is reporting the recent breaks of md4, md5, and sha-0, none of which are related to factoring. Our symmetric key cryptography is in some sense even shakier than our public key cryptography, because there's no simple mathematical primitive which it's based on.<br /><br />-BramAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1094336881879160912004-09-04T17:28:00.000-05:002004-09-04T17:28:00.000-05:00Hmmm... what are reasons why we "know" P!=NP. My ...Hmmm... what are reasons why we "know" P!=NP. My basic intuition is that NP-complete is "more complex" than P - presumably according to some complexity measure - but given the negative results about the ability of complexity measures to seperate complexity classes, that intuition seems just wrong.<br /><br />P!=NP and Con(ZF) are both useful assumptions allowing us to get on with practical cyptography and mathematics respetively. (Assuming P=NP would seem pretty useless - without an actual working algorithm, P=NP doesn't achieve anything).<br /><br />It's tempting to suggest a purely psychological explanation for our belief in both P!=NP and Con(ZF) - that we tend to blur the distinction between useful and true.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1094193197916317732004-09-03T01:33:00.000-05:002004-09-03T01:33:00.000-05:00The fact that "all mathematics is based on unprova...The fact that "all mathematics is based on unprovable assumptions about consistencies of logical theories" is true but not really very relevant. It's inconceivable that Peano arithmetic or Euclidean geometry is inconsistent (if I thought anyone seriously believed that, not simply in the role of devil's advocate, I would consider that person insane). Even if ZFC were inconsistent it's hard to imagine that it would cause more harm than amending an axiom, leaving 99.99% of all mathematics unchanged, the same way the contradictions in Frege's axioms caused no global problems in mathematics. By contrast, nobody could claim that P != NP is as obvious as the consistency of PA, and the consequences could be far more dramatic. (If P=NP, then even if no practical algorithms ever came out of it, a lot of modern complexity theory would look like wasted effort. Perhaps much of it could be salvaged to deal with finer distinctions than simply P vs. NP, and of course much of it deals with unrelated questions in the first place, but the consequences would still be huge.)Anonymousnoreply@blogger.com