Two great open questions from the early 70's:

- Is P≠NP?
- Who was Deep Throat?

Now that we

know
the answer to the latter, can a resolution of P versus NP be far
behind? I certainly hope the proof of P≠NP is not as anticlimactic
as finding out Deep Throat's identity.

P is neither equal to NP nor is it not equal to NP. They both just exist.

ReplyDeleteWell cripes, who did you think Deep Throat would be?

ReplyDeleteGerald Ford?

Pat Buchanan

ReplyDeleteWhat 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,

ReplyDeletecryptography, 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.

ReplyDeleteP: You killed my father!

ReplyDeleteNP: P, I am your father.

ReplyDeleteHow can a proof be anticlimactic?If someone were to prove P=NP to be formally independent. At least

Iwould 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).

ReplyDeleteSAT can be solved in O(n^Ackerman(100,100)) for all n <= log_2(Ackerman(100,100))

ReplyDeleteI've heard that Bob Woodward knows the proof for P=?NP, but he won't tell until the key participants have passed on.

ReplyDeleteAll the deep-throated witty comments aside, what can be disappointing or anti-climactic about the resolution of the P=NP question?

ReplyDelete1. 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:

ReplyDeleteNP 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":

ReplyDeleteMany 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.

ReplyDeleteI 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.

ReplyDelete