Thursday, June 02, 2005

Mysteries of the Seventies

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.

15 comments:

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

    ReplyDelete
  2. Well cripes, who did you think Deep Throat would be?

    Gerald Ford?

    ReplyDelete
  3. 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?

    ReplyDelete
  4. Dustin J. Mitchell10:28 PM, June 02, 2005

    Let's just hope the FBI isn't involved with the proof for P/NP.

    ReplyDelete
  5. P: You killed my father!
    NP: P, I am your father.

    ReplyDelete
  6. 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.

    ReplyDelete
  7. My personal version of "anticlimatic" (and maybe even downright irritating) would be a proof that SAT is solvable in n^Ackerman(100,100).

    ReplyDelete
  8. SAT can be solved in O(n^Ackerman(100,100)) for all n <= log_2(Ackerman(100,100))

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

    ReplyDelete
  10. 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?

    ReplyDelete
  11. 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

    ReplyDelete
  12. 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.

    ReplyDelete
  13. Many people are still unsatisfied with the proof of Fermat's Last Theorem, since only two people understand it.

    ReplyDelete
  14. 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.

    ReplyDelete