Not signed in (Sign In)

WorldWeird: P!=NP proof released

Bottom of Page

1 to 19 of 19

  1.  
    •  
      CommentAuthorArtenshiur
    • CommentTimeAug 8th 2010 edited
     (8709.1)
    Ladies and gentlemen, your bank accounts are safe. The venerable question of P vs NP has been (possibly) resolved by a single author out of HP Labs. Here's the paper.

    A rough perusal of the abstract doesn't raise any red flags, so this may actually be true. Thoughts?

    Never before have I been so happy to see an exclamation mark. (I misread it the first time around.)
  2.  (8709.2)
    Personally, glad that we've ruled out at least one of the various ways that society might tear itself apart.
  3.  (8709.3)
    Yes, if P != NP is true I will be happy.

    Although slightly disappointed as well.
  4.  (8709.4)
    I'm slightly excited about this.

    I'm not ecstatic because I know i'm not going to understand the proof.

    So... if you'd be so kind as to give me a rundown :D
    [seriously, i'll try and understand it first then come back and pester people]
    •  
      CommentAuthorcity creed
    • CommentTimeAug 9th 2010
     (8709.5)
    [seriously, i'll try and understand it first then come back and pester people]

    I have tried. I have failed.
    Can anyone explain in little words, for the benefit of us sensitive humanities students, why this is remarkable?
    • CommentAuthorxerox2k2
    • CommentTimeAug 9th 2010
     (8709.6)
    quoting wikipedia,cause i took university courses on this stuff and still don't understand half of it

    The P versus NP problem is a major unsolved problem in mathematics that is important in both theoretical computer science and mathematical logic. Informally, it asks whether every decision problem (a mathematics problem with a yes-or-no answer) whose solution can be efficiently checked by a computer can also be efficiently solved by a computer. It is considered by many theoretical computer scientists to be the most important problem in the field

    In essence, the question P = NP? asks:

    Suppose that "yes"-answers to a "yes"-or-"no"-question can be verified "quickly". Then can the answers themselves also be computed "quickly"?

    The theoretical notion of "quick" used here is that of an algorithm that runs in polynomial time, which usually but not always corresponds to an algorithm that is fast in practice. The general class of questions for which some algorithm can provide a yes-or-no answer in polynomial time is called "class P" or just "P".

    For some questions, there is no known way to find an answer quickly, but if one is provided with information showing that the answer is "yes" (known as a certificate, it may be possible to verify the certificate quickly. The class of yes-or-no questions for which a certificate can be verified in polynomial time is called NP.
    • CommentAuthorJayzor
    • CommentTimeAug 9th 2010
     (8709.7)
    Can anyone explain in little words, for the benefit of us sensitive humanities students, why this is remarkable?


    I'll have a go. I haven't looked at the purported proof beyond the introduction, so I can't really speak to what the author is doing. The proof may yet turn out to be flawed (i.e. not actually a proof); it was just released today, it's 102 pages, and it hasn't been reviewed by anyone other than the author. (I'm sure there are several people looking over it now, but 102 pages of math takes a lot longer to read than, say, 102 pages of a novel.) That said, the question is why this is remarkable (or at least, would be remarkable if the proof holds up).

    The P vs. NP question is easily the most important question in theoretical computer science today, and has been for a couple of decades now. It's one of the most important questions in the whole of mathematics even, as evidenced by its inclusion on the list of Clay Millenium Problems. Solutions to those come with a $1 millon prize, as you may have heard about when the last/only mathematician to solve one of them turned down the prize, so it's not just a nice trophy for someone's mantle. This really just establishes that people who aren't you think this is important, which may or may not be persuasive.

    Okay, so, the problem itself. There are a lot of problems that arise naturally that a computer can find solutions to quickly. ('Quickly' has a specific meaning here; it means the program runs in polynomial time (um), whence the P in P vs. NP.) Things like sorting a list of names fall into this category, as well as a lot of basic arithmetic. These are the things that we're happy to have a computer do for us, and it will do a good, fast job all of the time. But there are other problems that seem pretty natural that we don't know any fast way to program a computer to find a solution, but it's easy to check if a possible solution actually works. The common "real world" application people mention here is the traveling salesman problem: You have a salesman who wants to stop through several different cities, visiting each city exactly once, and you want to find the shortest possible way to do this. (Taking the US as an example, you don't want your salesman to go NYC->Seattle->DC->LA, crossing the country twice and generally having to travel much farther than something like NYC->DC->LA->Seattle.) You ask "Is there a route the salesman can take that is less than x miles?", where x is some number. If the answer is yes, this is easy to check: somebody provides you a route and you just calculate how far the salesman travels following this route. But finding such a route (using the algorithms we currently know) can take a very long time even for a small number of cities. More than 4, but by say 20 cities our best algorithms won't return an answer in anything resembling a reasonable amount of time. Anyways, this class of problems (where we can check solutions quickly, but not necessarily find them quickly) is NP. (Some people will tell you NP stands for "non-polynomial"; it doesn't, but knowing what it actually stands for isn't helpful for the sensitive humanities student.)

    Maybe we're just not clever enough, though, and there's a fast algorithm for even NP problems. In this case, P=NP. This would be shocking for a lot of reasons, although admittedly the biggest one is, "Well, we've tried for a long time and nothing's worked yet." Most people believe that P!=NP, as it seems to gel with our intuitions about solving the two types of problems, so the purported result wouldn't be surprising in that sense. On the other hand, there are provably quite a few obstacles to finding a proof of P!=NP (these obstacles are rather technical, but they are doozies, really), so if this proof works, it represents a huge advance in the state of the art for dealing with these types of questions. That's why this would be remarkable; if the proof works, it must have a good chunk of genuinely new mathematics that should give us insight into a host of other questions.

    tl;dr The P vs. NP problem is a about the very basic question of whether or not solving certain types of problems is actually harder than solving other types, or if most of the problems we care about take more or less the same amount of work to solve and we're just too stupid to have figured it out by now. It's a question about the fundamental limitations of our problem-solving techniques, and if this proof is correct, it would represent a big leap in our understanding of what makes some problems harder than others.
  8.  (8709.8)
    These descriptions give good background, but they don't approach why P=NP is a bad thing and why P!=NP is a good thing.

    The reason is that modern forms of encryption rely on the idea that the encryption is hard to solve unless you have the encryption key. I.e., it's NP if you're trying to crack it, and therefore hard. If you have the key, it's P, and you're good.

    So if P=NP, it could mean that all encrypted systems are a bajillion times more vulnerable to spies/thieves/whatever than was previously considered. That could lead to the collapse of the banking system, to name one of the *less* critical things it might destroy.

    I know computer scientists who have P=NP "disaster" plans that rival even the government's best nuclear winter survival plans.

    Therefore, P!=NP is very good news. If true.
    • CommentAuthorJayzor
    • CommentTimeAug 9th 2010 edited
     (8709.9)
    @John Skylar

    That's overstating things a little. Factorization (which most modern day encryption is based on) is NP-hard, and so it is correct that if P=NP, there would be some relatively quick (compared to our current algorithm) way to factor numbers. But there are a few reasons that you don't need to stock up on canned food if it's the case.

    1. Relatively quick is not the same as absolutely quick. Polynomial time is in theory fast, and it's much faster than exponential time, but in practice if the algorithm is above O(n^3) or O(n^4) (which could easily, easily happen; for example there's a polynomial time algorithm for recognizing prime numbers that is too slow to use in practice), it's not fast enough to be useful for factoring.

    2. There are encryption schemes not based on factorization; they are well-known and well-studied, just rarely implemented because the factorization stuff is easier/faster for now. People would switch if the factorization stuff wasn't good enough.

    3. And anyways, we know for a fact that a quantum computer can factor numbers in polynomial time regardless of the outcome of the P vs. NP problem. So if your friends are worried about P=NP for that reason, they should be even more worried about the possibility of a working, nontrivial quantum computer being built. This problem has led to the development of quantum cryptography.

    I think P=NP would be bad because it would mean that we really have no idea what makes a problem hard. At all. That's not as sexy as saying "OH NOES TEH HAX" to some people, but hey, I like this stuff because it's about the limits of human knowledge, not because it lets me shop on Amazon.

    Edit: Of course, I'm just realizing that you could be talking about more general methods of encryption than those based on factorization. Yes, I think those will be affected too, but similar caveats apply. Polynomial time is theoretically fast, but in practice, things that run in polynomial time can still be too slow to compute.
  10.  (8709.10)
    Just came across this interesting article from The Reference Frame (an interesting blog with a terrible design)

    http://motls.blogspot.com/2010/08/hp-labs-researcher-p-is-not-np.html

    two possible mistakes are given at the bottom.
    •  
      CommentAuthorcity creed
    • CommentTimeAug 10th 2010
     (8709.11)
    Thanks for the breakdowns, I can at least now start to grasp roughly what the issue is and why it matters.
    Cheers!
    •  
      CommentAuthorArtenshiur
    • CommentTimeAug 10th 2010
     (8709.12)
    @Jayzor: Factorization is not known to be NP-hard. It may well even be in P. If we knew it were NP-hard, Schor's algorithm plus this paper would definitively disprove the Church-Turing thesis for quantum systems, and that's not something I'm going to take for granted. Also, a thing can be outside of P, and in NP, and not be NP-hard. (Also, a thing can be outside NP and be NP-hard. "NP-complete" refers to things which are in NP and are NP-hard.)

    Yes quantum computers could, theoretically, in the future, crack encryption. I'd point out that the largest number we have yet to factor via that method is 15, and that was incredibly difficult. And larger scale systems are turning out to be much, much harder. And would be very expensive for a long time. And every quantum computer would constantly be in use for academic purposes for a very long time. Etc. This would give us plenty of time to prepare.

    P=NP, on the other hand, would allow reductions from anything in NP to something in P. This knowledge could be trivially spread. Some idiot fourteen year old in Romania could easily get his hands on it and decide to start emptying bank accounts.

    The argument "polynomial time can be slow" has been empirically observed to be pretty much completely false. Once it's in P, we can do it quickly. Almost universally. While this might be an impediment, it probably wouldn't be.

    Quantum cryptography requires an entire new infrastructure. I wouldn't depend on that too hard. And yes, there are other techniques that are not in NP to crack. They are also not widely implemented, and would take time to be installed in critical systems.

    And I don't really understand what you mean when you say that P=NP would mean "we really have no idea what makes a problem hard" for two reasons. What makes a problem hard is the amount of time it takes to solve the problem, relative to the size of the input. That's how we define it in computer science. Also, P and NP are hardly the only complexity classes. Check out the Complexity Zoo to see how many people talk about. BPP is an important one. Or, for example PSPACE. It wouldn't really be much of a hit to what we know. It would mostly be a hit to our egos, for not finding the reduction sooner. Oh, and also banking and such.
  13.  (8709.13)
    this is just a quick one as I don't have much time, but I thought a lot of prime factorization was based off the if the reimann hypothesis can be proven or not?
    • CommentAuthorZJVavrek
    • CommentTimeAug 10th 2010
     (8709.14)
    First, I thank those who have given explanations. I've been wondering for a while what P=NP meant.

    My mind didn't go to the doomsday scenarios--a sign of my lack of computer science education (the cryptography issue makes perfect sense, I simply hadn't thought about it.) Instead, I wondered what benefits we might get out of this, and realized that (again, lack of CS familiarity) I frankly had no idea how P=NP could help us, but I was sure that it had to have practical, beneficial applications. What might those be? Am I wrong?
    •  
      CommentAuthorArtenshiur
    • CommentTimeAug 11th 2010
     (8709.15)
    P=NP would have plenty of practical, beneficial applications, in that we could solve a whole new class of problems in a tractable way. It would, for example, make airline scheduling much more efficient. It would also allow for much smarter AIs. Many industrial design problems would be made much easier, allowing for better consumer products. Internet routing, machine learning, data mining... nearly everything would be affected. But it appears none of that will come to pass. P!=NP, which is what was proved, is only practically applicable in telling us that those things will not happen. This is why we are a little bit disappointed to hear this, though also relieved.
    • CommentAuthorJayzor
    • CommentTimeAug 11th 2010
     (8709.16)
    @Artenshiur

    Ah yeah, factorization is weirdly placed (or not placed, I guess) in the hierarchy of complexity classes. I always forget that. Thanks for the clarification. And I specifically mentioned "nontrivial" quantum computers because yes, I know that what we have currently is only capable of factoring 15. I wasn't really making any sort of argument regarding the feasibility of quantum computing or cryptography, just that if you're worried about P=NP destroying our banking infrastructure you might as well be worried about quantum computing. Which is to say that I'm not particularly worried about either possibility, honestly.

    And really, polynomial time can be quite slow. When's the last time you heard about somebody implementing the AKS algorithm for recognizing primes? It's something like O(n^8), meaning it's completely useless on the numbers that we want to test for primality. Hence the use of things like the Miller-Rabin test. If we find an algorithm for 3SAT which is O(n^1000), although that's polynomial time, it's not of any practical use, and we'd probably just stick to the heuristic methods we know.

    Finally, I agree, run-time is how we determine how hard a problem is now. But if P=NP, then the traveling salesman problem is in that sense as hard as sorting a list of values. Does that seem right to you? It doesn't to me; one is clearly harder than the other. But if P=NP, then my (and most people's) intuition about what problems are hard is either totally wrong (i.e. the two are as hard as each other, and we were completely wrong about it this whole time) or based on something other than run-time (which would be interesting, but would also mean we're looking at the "wrong" thing this whole time). Either way, we would have been doing something wrong when talking about how hard a problem is this whole time. That's what I meant when I said it would mean we have no idea what makes a problem hard. I hope that makes sense.
    •  
      CommentAuthorArtenshiur
    • CommentTimeAug 11th 2010 edited
     (8709.17)
    @Jayzor: My point regarding quantum computation is that the infrastructure susceptible to factorization would have plenty of time to see a quantum computation attack coming, for the reasons listed above, and so it wouldn't really be a problem, whereas an efficient NP reduction could have a blitzkrieg effect. Just saying, they're not equivalent threats.

    I won't argue that polynomial time can't be slow, but the majority of the time it isn't and when it is it usually gets reduced eventually, so I don't find it to be a likely issue.

    I see where you're coming from regarding intuition about hardness, but I don't think that breaks down quite so much. I doubt traveling salesman will ever be reduced to O(n log(n)); the intuitive hierarchy of hardness would remain, just without that dividing line. Plus, there are plenty of classes larger than NP.

    Edited for grammar.
  18.  (8709.18)
    @Artenshiur
    I hate to be the dick but, P=NP doesn't make anything simpler and doesn't have any benefits, it mearly states that you CAN make things simpler, quicker [deterministic].

    Traveling salesman is NP-Hard and so P=NP doesn't affect it.

    None of this really matters, if P=NP it doesn't mean we're suddenly going to find a series of algorithms to calculate the NP problems in deterministically (I guess this reiterates what I said previously)
    •  
      CommentAuthorArtenshiur
    • CommentTimeAug 11th 2010
     (8709.19)
    Strictly speaking, PintSized, you're right, P=NP doesn't automatically give us any algorithms. However, we expect that a proof that P=NP would most likely consist of a reduction of some NP-hard problem to polynomial time. That's the situation we're really talking about, and in it you instantly have a practical reduction of all problems in NP to polynomial time, by the definition of "NP-hard".

1 to 19 of 19

  1.