Inside everybody's favorite million-dollar math proof

Discuss

29 Responses to “Inside everybody's favorite million-dollar math proof”

  1. Anonymous says:

    I am a huge fan of the argument put forward above that P ≠ NP:

    “I’m very, very smart, and if I haven’t figured out how to solve this problem well, clearly noone can.”

  2. Anonymous says:

    42 is the answer.

  3. MrWoods says:

    First Sorting in-sound, now P != NP. Boing Boing are you wooing the computer geeks after the whole Software Developer != Engineer debacle? I feel like I’m on slashdot, but with better layout.

  4. Anonymous says:

    Ar-aggh. P = NP does not mean ‘NP = easy’.

    If the optimal solution to monotone one-in-three SAT is n^500000 it is not ‘easy’ in any time/space-local sense. Nor would we have ‘noticed it’, nor would we be expected to come up with that algorithm, nor will we be expected to in the near future.

    I’m tired of the continuous repeating of these /terrible/ arguments.

  5. Anonymous says:

    Could it be that in some circumstances P=NP and others it does not, depending on the solution itself?

  6. hymie says:

    P vs. NP is not about which problems cannot be solved – all problems in both P and NP can be solved, but problems in P have a solution time that’s proportional to some power of the size of the input. If NP is not P, then some problems in NP would require a solution time that’s higher than any power of the size of the input, exponential, for example.

    Now, everyone expects that P and NP are different, so the value of a proof isn’t the demonstration of that so much as the new mathematical techniques that will be required for it.

    One reason P vs. NP is so difficult is that it has been demonstrated that many different proof techniques are guaranteed to fail because we can construct theoretical augmented computational universes in which P vs. NP is provably true or provably false and those proof techniques fail to distinguish between the aspects of those augmentations that make the difference.

  7. monstrinho_do_biscoito says:

    ok, nowhere in this whole article and the comments and the original article does it mention what the letters P and NP denote. i’m gonna guess Programable and Nonprogramable?

    • sabik says:

      nowhere in this whole article and the comments and the original article does it mention what the letters P and NP denote

      Probably better to just think of them as “P” and “NP”, because the letters stand for “polynomial [time]” and “non-deterministic polynomial [time]“, which wouldn’t help anyone anyway.

      P is a class of problems that are easy to compute (for a particular technical definition of “easy”).

      NP is the class of problems where checking a “yes” answer is P.

      For instance, checking whether you can visit a given list of cities (in any order) on a single tank of gas is NP, because once you have an ordering of the cities that lets you do that, adding up the distances is easy (that is, P). However, nobody knows whether you can come up with an ordering like that easily; nobody’s ever found a way. (This is the “Travelling Salesman Problem”.)

      It has been proven that this particular problem is among the hardest in NP, so if you solve this one in easily, you can solve them all. (Called “NP-complete”.)

    • Niklas says:

      it has actually been written a few places here that P is “polynomial” but not NP that is… Hey, why didn’t you klick on the Wikipedia link that Ben supplied? It explains it all from the beginning.

  8. Anonymous says:

    In retrospect, all NP are P.

  9. shadowfirebird says:

    I’ve been a professional programmer for 20 years, and I this P=NP thing means nothing to me, either.

    Okay, I know what the traveling salesman problem is (because someone asked me to code a “quick report” to solve it once!) and I get that it’s an example of an NP problem.

    The Wikipedia page is quite good, even though it flashes around mathematical terms like crazy.

    My first take on this whole thing is that most of the problems I have to solve in my work are NP anyway, and will stay that way. I guess P=NP is important if you are writing a compiler, but to the everyday programmer, I wonder if it really matters…

  10. Fee says:

    In good journalism, you assume no knowledge on the part of the reader, and explain any abbreviations. If you have to go elsewhere to get explanations, that’s a fail.

    I’d suggest the same rules for professional bloggers also.

  11. jtf says:

    I appreciate the attempt to give the picture an MIT touch. Too bad you couldn’t find a picture of a stoned-looking math geek wearing a proper Florey shirt.

  12. Quaternion says:

    In their attempts to make the material somewhat accessible, many (most?) media accounts of the attempted P != NP proof completely botched the description of complexity classes P and NP (and some even went so far as to claim that the problem is now solved, ie. they just assumed that the proof is correct). In this case, a link to Wikipedia would have been better. The language is technical because the problem is very precisely defined, and getting loose with the language can very quickly lead to statements that are vague/different/false. Given all of this, I think this summary on Boing Boing that just quotes John Pavlus actually provides one of the more responsible descriptions of the problem that I’ve seen.

    If you’d like to know more about P vs NP and the fundamental limits of computation, I’d also recommend this article by Neil Immerman in the Stanford Encyclopedia of Philosophy. It assumes some mathematical experience (eg. set notation shouldn’t scare you), but it is otherwise accessible requiring no background knowledge in the area:
    http://plato.stanford.edu/entries/computability/
    It lays out a good path to understanding P vs NP in its proper mathematical and historical context (warning: don’t try to read math stuff at your normal reading pace…)

  13. jimh says:

    Dirk: All right, now you’re talking above my head.
    I don’t know this industry jargon… P, NP… whatever.

    All I know is that I cannot get a record contract. We cannot get a record contract
    unless I take these tapes…

    Todd: and granted, the tapes themselves are your…

    Dirk: You own them, OK? But the magic that is on the tapes…

    Todd: That fuckin’ heart and soul we put into those tapes… that is ours, and you don’t own that.

    Dirk: I need to take that magic and get it to the record company. And they’re waiting for us.

    Todd: We were supposed to be there a half-hour ago. We look like assholes right now, man!

  14. Rodney Hoffman says:

    You write: “The proof offered … isn’t standing up very well against scrutiny…” Can you provide a reference or two?

    Thanks.

  15. Anonymous says:

    Most people believe that P /= NP, and that there aren’t shortcuts for NP problems.

    But take a look at primality tests, and you’ll see that they did find a shortcut, jumping from NP to P.

  16. Anonymous says:

    Anon #5: Primality was in RP, not NP. The big primes in P result was a derandomization of a random argument. That’s miles easier than proving anything about P ? NP

    • Anonymous says:

      Yes. NP is the class of problems for which, once you have a solution, you can confirm that it is the correct solution with an algorithm in P. One of the subsets of NP is P – problems for which the solution can be found with an algorithm of polynomial complexity. It should be easy to see that all problems in P are also in NP, because if you can find a solution in P, obviously you can confirm it in P. So, having established that P is a subset of NP, there are two possibilities: either P is a proper subset of NP, meaning that there are problems which cannot be solved in P but whose solutions can be confirmed in P, or NP is also a subset of P, and so the two sets are equal. Another subset of NP are the NP complete problems – if P != NP, then at least all the NP complete problems are in NP and not in P; if any NP complete problem is in P, all NP problems are in P and so P=NP. However, Turing himself proved that some problems simply cannot be solved – and uncomputable problems that cannot be solved by UTM arevery different from the intractable or as Knuth called them Herculean NP problems that can be solved by UTM but take a *long* time-, and Matisyaev (?) proved that the general Diophantine equation cannot be solved, and Wiles that x^n + y^n = z^n can’t be solved for n > 2; so even if N = NP, there will always be some problems that cannot be computed. Finally, integer factorization may be sub-exponential (not P) without a quantum computer (or there may be a polynomial algorithm without a quantum computer – but I doubt that just like I doubt that there’s a true sort algorithm in O(n) – and radix sort doesn’t count), but NOBODY ever argued that factorization was NP-complete.

  17. Maggie Koerth-Baker says:

    Rodney, there’s more on that in the story at Technology Review that is linked here.

  18. Phikus says:

    As I understand it, an NP problem is No Problem at all. =P

  19. Chris Furniss says:

    Huh?

  20. David Carroll says:

    I have a truly marvellous demonstration of this proposition which this BB comment is too small to contain.

  21. Jonathan says:

    There’s a sweet metastory in which this lack-of-proof played a part: the MSM is giving significant ink to The Power of Collaboration in math/science advances. Imagine!

    See NYT: Debate Over P vs. NP Proof Highlights Web Collaboration:

    “The potential of Internet-based collaboration was vividly demonstrated this month when complexity theorists used blogs and wikis to pounce on a claimed proof for one of the most profound and difficult problems facing mathematicians and computer scientists.”

    And, same week, front page in NYT: Rare Sharing of Data Led to Results on Alzheimer’s:

    “The key to the Alzheimer’s project was an agreement as ambitious as its goal: not just to raise money, not just to do research on a vast scale, but also to share all the data, making every single finding public immediately, available to anyone with a computer anywhere in the world.”

  22. Roy Trumbull says:

    9^N + 4^N = 5. You can do it by inspection or substitution. Otherwise be prepared to waste a lot of time.
    Using an infinite series you might get .4999999999999999999999999 etc. for an answer.

  23. codesuidae says:

    The “P versus NP problem” asks whether these two classes are actually identical; that is, whether every NP problem is also a P problem.

    It seems more like it’s asking whether all NP problems are just P problems for which we haven’t yet found at least one P-type solution.

    For them to be identical all P problems would also have to be NP problems. I’m not sure if that is true, we may need a committee of politicians to advise us on that.

Leave a Reply