Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
P is neither equal to NP nor is it not equal to NP. They both just exist.
Well cripes, who did you think Deep Throat would be? Gerald Ford?
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,cryptography, banking, ... all for different reasons.Proof is either correct or incorrect. The theorems are interesting, surprising,disappointing, anticlimactic to one's assumptions .... How can a proof be anticlimactic?
Let's just hope the FBI isn't involved with the proof for P/NP.
P: You killed my father!NP: P, I am your father.
How can a proof be anticlimactic?If someone were to prove P=NP to be formally independent. At least I would consider it quite anti-climactic.
My personal version of "anticlimatic" (and maybe even downright irritating) would be a proof that SAT is solvable in n^Ackerman(100,100).
SAT can be solved in O(n^Ackerman(100,100)) for all n <= log_2(Ackerman(100,100))
I've heard that Bob Woodward knows the proof for P=?NP, but he won't tell until the key participants have passed on.
All the deep-throated witty comments aside, what can be disappointing or anti-climactic about the resolution of the P=NP question?1. If NP-complete problems are in P and the polynomial for the running time has a high degree. 2. If P<>NP but the running time is a low-degree polynomial for "most" problem instances. Would this be disappointing? 3. "If someone were to prove P=NP to be formally independent." I am not sure what exactly this means. 4. What else?
Here's one disappointing scenario: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.--boaz
As an example of a "disappointing proof":Many mathematicians were disappointed by the proof of the Four Color Theorem: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.
Many people are still unsatisfied with the proof of Fermat's Last Theorem, since only two people understand it.
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.