tag:blogger.com,1999:blog-3722233.post111771090619102160..comments2021-03-01T13:59:11.893-06:00Comments on Computational Complexity: Mysteries of the SeventiesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-3722233.post-1117977629226618082005-06-05T08:20:00.000-05:002005-06-05T08:20:00.000-05:00I don't think this is the case. FLT has been decom...I don't think this is the case. FLT has been decomposed into a sequence of lemmas and theorems each of which is well understood. Last I heard there is a 21 page proof out there and the entire proof outline fits in a t-shirt.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117967926841836652005-06-05T05:38:00.000-05:002005-06-05T05:38:00.000-05:00Many people are still unsatisfied with the proof o...Many people are still unsatisfied with the proof of Fermat's Last Theorem, since only two people understand it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117924495990389432005-06-04T17:34:00.000-05:002005-06-04T17:34:00.000-05:00As an example of a "disappointing proof":Many math...As an example of a "disappointing proof":<BR/><BR/>Many mathematicians were disappointed by the proof of the Four Color Theorem:<BR/>it is a huge proof by cases (hundreds of them) and it did not yield an insight as to what makes planar graphs 4-colorable. At least, not yet.Janos Simonhttps://www.blogger.com/profile/15677985672817404601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117900008884384602005-06-04T10:46:00.000-05:002005-06-04T10:46:00.000-05:00Here's one disappointing scenario:NP not contained...Here's one disappointing scenario:<BR/>NP not contained in SUBEXP and P=BQP, but you still have to learn quantum computing to understand even the proof of the first statement.<BR/><BR/>--boazAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117854925217915272005-06-03T22:15:00.000-05:002005-06-03T22:15:00.000-05:00All the deep-throated witty comments aside, what c...All the deep-throated witty comments aside, what can be disappointing or anti-climactic about the resolution of the P=NP question?<BR/><BR/>1. If NP-complete problems are in P and the polynomial for the running time has a high degree. <BR/><BR/>2. If P<>NP but the running time is a low-degree polynomial for "most" problem instances. Would this be disappointing? <BR/><BR/>3. "If someone were to prove P=NP to be formally independent." I am not sure what exactly this means. <BR/><BR/>4. What else?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117824156194271712005-06-03T13:42:00.000-05:002005-06-03T13:42:00.000-05:00I've heard that Bob Woodward knows the proof for P...I've heard that Bob Woodward knows the proof for P=?NP, but he won't tell until the key participants have passed on.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117812486590404192005-06-03T10:28:00.000-05:002005-06-03T10:28:00.000-05:00SAT can be solved in O(n^Ackerman(100,100)) for al...SAT can be solved in O(n^Ackerman(100,100)) for all n <= log_2(Ackerman(100,100))Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117809760406731702005-06-03T09:42:00.000-05:002005-06-03T09:42:00.000-05:00My personal version of "anticlimatic" (and maybe e...My personal version of "anticlimatic" (and maybe even downright irritating) would be a proof that SAT is solvable in n^Ackerman(100,100).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117801574448127612005-06-03T07:26:00.000-05:002005-06-03T07:26:00.000-05:00How can a proof be anticlimactic?If someone were t...<I>How can a proof be anticlimactic?</I><BR/><BR/>If someone were to prove P=NP to be formally independent. At least <I>I</I> would consider it quite anti-climactic.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117772882349272792005-06-02T23:28:00.000-05:002005-06-02T23:28:00.000-05:00P: You killed my father!NP: P, I am your father.P: You killed my father!<BR/>NP: P, I am your father.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117769289420973082005-06-02T22:28:00.000-05:002005-06-02T22:28:00.000-05:00Let's just hope the FBI isn't involved with the pr...Let's just hope the FBI isn't involved with the proof for P/NP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117744596457395542005-06-02T15:36:00.000-05:002005-06-02T15:36:00.000-05:00What do you mean by a proof being anticlimactic? I...What do you mean by a proof being anticlimactic? I think the world would be happy to have an answer either way. People in complexity theory, algorithms,<BR/>cryptography, banking, ... all for different reasons.<BR/><BR/>Proof is either correct or incorrect. <BR/>The theorems are interesting, surprising,<BR/>disappointing, anticlimactic to one's <BR/>assumptions .... <BR/><BR/>How can a proof be anticlimactic?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117733920284290142005-06-02T12:38:00.000-05:002005-06-02T12:38:00.000-05:00Pat BuchananPat BuchananAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117730348521997362005-06-02T11:39:00.000-05:002005-06-02T11:39:00.000-05:00Well cripes, who did you think Deep Throat would ...Well cripes, who did you think Deep Throat would be? <BR/><BR/>Gerald Ford?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1117723679849410722005-06-02T09:47:00.000-05:002005-06-02T09:47:00.000-05:00P is neither equal to NP nor is it not equal to NP...P is neither equal to NP nor is it not equal to NP. They both just exist.Anonymousnoreply@blogger.com