Forgot your password?
typodupeerror
Math Science

Possible Issues With the P != NP Proof 147

Posted by Soulskill
from the intuitively-obvious-to-the-most-casual-observer dept.
An anonymous reader writes "We previously discussed news that Vinay Deolalikar, a Principal Research Scientist at HP Labs, wrote a paper that claimed to prove P is not equal to NP. Dick Lipton, a Professor of Computer Science at Georgia Tech, analyzed the idea of the proof on his blog. In a recent post, he explains that there have been many serious objections raised about the proof. The post summarizes the issues that need to be answered in any subsequent development, and additional concerns are raised in the comment section."
This discussion has been archived. No new comments can be posted.

Possible Issues With the P != NP Proof

Comments Filter:
  • What? (Score:1, Interesting)

    by lawnboy5-O (772026) on Wednesday August 11, 2010 @01:38AM (#33212634)
    I haven't been this confused since reading Godel's Proof.
  • Incompleteness (Score:5, Interesting)

    by im_thatoneguy (819432) on Wednesday August 11, 2010 @01:40AM (#33212642)

    Yes there can be a proof to prove that there is no proof. Check out Godel's Incompleteness Theorem

    http://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_theorems [wikipedia.org]

    Gödel's incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems for mathematics. The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics. The two results are widely interpreted as showing that Hilbert's program to find a complete and consistent set of axioms for all of mathematics is impossible, thus giving a negative answer to Hilbert's second problem.

    Not sure if any such effort exists though in this case.

  • Hard core (Score:5, Interesting)

    by gregrah (1605707) on Wednesday August 11, 2010 @02:38AM (#33212810)
    "Formal Language Theory" - an undergrad course at my university that dealt with Finite State Automata, Touring Machines, Computability Theory, Complexity Theory, and the formal proofs thereof, was the most interesting class that I've ever taken. That being said, I always felt when doing homework for that class that I was taking a dive off the deep end (i.e. pushing the limits of human sanity). And that's only from studying the "low hanging fruit" that people were publishing papers on several decades ago when theoretical computer science was still relatively young. I can't imagine things have gotten any less mind-warpingly complex since then.

    I have tremendous respect for the folks who continue to "dabble" in this stuff. I'm sure that for their efforts they have been rewarded with glimpses of indescribably beautiful works of both man and of nature.
  • Re:Incompleteness (Score:1, Interesting)

    by Anonymous Coward on Wednesday August 11, 2010 @02:54AM (#33212856)

    Here's a proof short enough to reproduce in a comment. http://www.win.tue.nl/~gwoegi/P-versus-NP/argall.txt [win.tue.nl]

    P=NP - An impossible question
    A proposed proof of undecidability by Nicholas Argall, 25 March, 2003.

    There has been much debate surrounding answers to the question of P=NP.
    The problem is that we cannot answer the question until we have successfully
    asked the question. The question is impossible to ask, that it why it will
    never be answered.

    1) A provable answer to the question P=NP requires a complete and consistent
    formal statement of the question.
    Rationale: Hopefully, this is self-evident. It is certainly axiomatic that
    a formally provable statement be expressed in formal terms. Completion and
    consistency follow from the requirement to provide a proof that is not
    subject to challenge.

    2) A complete and consistent formal statement of the question must
    incorporate a complete and consistent formal definition of the sets P and NP
    Rationale: Hopefully, this is also self-evident. (I have left out the
    requirement to define the equality operator, since it is defined for us by
    set theory.)

    3) A definition based on a potentially undetectable characteristic is
    incomplete
    Rationale: We cannot accept the definition of the set NP purely in terms of
    its members having a property (a solution test in polynomial time) that we
    have no reliable mechanism to detect. Therefore, a complete definition of
    the set NP must be arrived at via some other means.

    4) The only possibility for a complete definition of the set NP is a
    language
    Rationale: Once we rule out observation of characteristics, our only means
    towards a definition of the set NP is to formulate a language, a procedure
    for testing the formal expression of the candidate problem that will accept
    the problem or reject it.

    5) No formal language capable of expressing non-trivial mathematical
    problems can be consistent and complete
    Rationale: As proven by Godel.

    6) Therefore, no consistent and complete definition of the set NP is possible
    Rationale: If we accept that the set NP can only be rigorously defined via a
    language, this conclusion follows from the premises above.

    7) Therefore, no consistent and complete statement of the problem of P=NP is
    possible
    Comment: A conclusion which is not only proven in this paper, but supported
    by the years of argument between mathematicians regarding the relevance of
    proposed answers to the problem.

    8) Therefore, P=NP is undecidable
    Comment: Given our inability to ask, we are unable to answer.

  • Re:Algorithms (Score:3, Interesting)

    by Anonymous Coward on Wednesday August 11, 2010 @05:29AM (#33213356)

    How about this simplification:

    P is the class of problems for which you can get the answer (output) quickly (i.e. in polytime).

    NP is the class of problems for which you can verify an answer quickly.

    P = NP is the question of whether all problems where you can verify the answer quickly have corresponding solvers that also find the answer quickly. If yes, P = NP, if not, P != NP. It's really a question about how powerful algorithms can be - and thus how powerful intelligence can be, because if P = NP, you could build a puzzle solver that would solve just about any puzzle, including "is there a short proof for [insert conjecture here]?".

  • Re:Algorithms (Score:1, Interesting)

    by Anonymous Coward on Wednesday August 11, 2010 @05:54AM (#33213466)

    Thank you.

    Also, thinking of that just blew my mind. Now I hope that P == NP would really be true because of all the possibilities...

  • by 2obvious4u (871996) on Wednesday August 11, 2010 @08:29AM (#33214552)
    Finding a proof for P=NP or P!=NP?

    In one case encryption can be proven secure, in the other we loose encryption but gain efficiency. What would be better for humanity going forward, being able to solve box packing problems instantly or having nearly perfectly secure communication?
  • Problem solving (Score:3, Interesting)

    by Fractal Dice (696349) on Wednesday August 11, 2010 @08:36AM (#33214648) Journal

    Can the proof be verified in polynomial time?

    I'm one of those ex-mathamaticians who still sulks at the existence of discussions beyond my ability to comprehend, where there is absolutely nothing constructive I can add. As a student back in the day, I was always nervous of proofs that were longer than a page - it always seemed to me that once a single proof got beyond a certain length, there was always some lingering doubt that some flaw or special condition had been overlooked, doubt that would pass on to every result that then used it. I guess that's the difference between learning math (where the problems are deliberately selected by textbook authors to have nicely bounded complexity) and researching math (where nobody knows how many twists and turns there are in the road between you and your goal).

I am not now, nor have I ever been, a member of the demigodic party. -- Dennis Ritchie

Working...