Slashdot Mirror

← Back to Stories (view on slashdot.org)

New Work Suggests That P Is Not Equal To NP (arxiv.org)

Posted by msmash on from the this-changes-everything dept.

New submitter cccc828 writes: In a new paper Norbert Blum tackles the P=NP question and finds them to be not equal. While this is exciting news (for theoretical computer scientists at least), remember that there is a long list of findings pointing either way.

80 of 147 comments (clear)

  1. Wow by DontBeAMoran · · Score: 1

    And all these years we've been using PnP computer hardware and PNP transistors.

    --
    #DeleteFacebook
    1. Re:Wow by Ungrounded+Lightning · · Score: 1

      And all these years we've been using PnP computer hardware and PNP transistors.

      Those were junction transistors. If P=NP there wouldn't be a junction.

      --
      Bantam Dominique roosters crow a four-note song. Once you've heard it as "Happy BIRTHday" you can't NOT hear it that way
    2. Re:Wow by cyberchondriac · · Score: 1

      That statement is so "dope". ba dum tish.

      --

      Look back up at my post, now look back down, you're on the Internet. Now look back up. I'm a signature.
  2. "While this is exciting news" by Stormy+Dragon · · Score: 3, Informative

    Since P != NP is the expected answer, is this news really that exciting? Evidence that P = NP is the one that would actually be exciting, since it would suggest the existence of an unknown algorithm that handles certain problems far more efficiently than the currently known alternatives.

    1. Re:"While this is exciting news" by dmgxmichael · · Score: 5, Insightful

      The expected answer means we will have cryptographic security available indefinitely. We may have to keep switching algorithms, but in principle there will always be an algorithm out there that can't be quickly bypassed. Evidence that P = NP (or one is a subset of the other) means all cryptography is doomed to fail.

    2. Re:"While this is exciting news" by Rei · · Score: 1

      Well, at least we'll find out the answer eventually. ;)

      --
      Ever since, I've been suspicious of Jesus and very careful around chlorine.
    3. Re:"While this is exciting news" by Anonymous Coward · · Score: 1

      Um, no.

      At best what you're talking about is using quantum mechanics to perform nondeterminism, Effectively, solving an NP problem with an NP algorithm. What humanity doesn't have now is a way to write and compute NP algorithms.

      It is absolutely amazing how many complete idiots like you read a 1 page pop-culture summary of quantum mechanics and P=NP and think that's the equivalent of a graduate degree in the field.

    4. Re:"While this is exciting news" by Stormy+Dragon · · Score: 5, Informative

      or one is a subset of the other

      P is already known to be a subset of NP. The question is whether it is a proper subset (P != NP) or not (P = NP).

      Evidence that P = NP means all cryptography is doomed to fail.

      Exciting news is obviously not always good news.

    5. Re:"While this is exciting news" by locofungus · · Score: 2

      The expected answer means we will have cryptographic security available indefinitely.

      I assume you're talking about asymmetric encryption. (Correctly used) OTP already gives perfect security symmetric encryption.

      We may have to keep switching algorithms, but in principle there will always be an algorithm out there that can't be quickly bypassed.

      Does this follow? AFAIAA all public key encryption requires a "trapdoor function" and I'm not aware of any that are NP Complete. Unless something has changed in the many years since I last looked at this that means that it's perfectly possible for P!=NP but there is no safe public key encryption method.

      Evidence that P = NP (or one is a subset of the other) means all cryptography is doomed to fail.

      I'm not sure even this is true for public key cryptography - what if factoring was found to be in P but with a polynomial of order 10^300. Then the RSA algorithm could be safe for sufficiently large primes even if P==NP

      --
      God said, "div D = rho, div B = 0, curl E = -@B/@t, curl H = J + @D/@t," and there was light.
    6. Re: "While this is exciting news" by Anubis+IV · · Score: 2

      Actually, the article isn't about P=NP or not in general. [T]he summary [...] specifically states that this P!=NP is proved only for a (very) specific problem.

      All it takes to prove once and for all that P!=NP in general is a single counterexample to the claim that P=NP. If you can prove that P!=NP for any problem, you would have succeeded in proving that P!=NP at all, given that you showed there was an item in P that does not exist in NP.

      It's like if I claimed that all hamsters are brown. Even a single counterexample would be sufficient to disprove my claim in general. Sure, there may be plenty of examples of brown hamsters, but proving that even one non-brown hamster exists would be sufficient to disprove the notion that ALL hamsters are brown. Likewise, just because some P problems can be solved in polynomial time (i.e. we know there's overlap between the P and NP sets, just like we know that many hamsters are brown), being able to prove that even a single counterexample exists would prove that the two aren't the same.

    7. Re:"While this is exciting news" by HornWumpus · · Score: 1

      If P = NP then P * N ^ 100 = P * N ^ 99 = P

      --
      John McAfee 'It was like that time I hired that Bangkok prostitute; to do my taxes, while I fucked my accountant'
    8. Re: "While this is exciting news" by HornWumpus · · Score: 3, Insightful

      It only takes one specific example to disprove a general proposition.

      They can still prove that P = NP for specific cases, but if this proof holds up, the general case is disproven.

      --
      John McAfee 'It was like that time I hired that Bangkok prostitute; to do my taxes, while I fucked my accountant'
    9. Re: "While this is exciting news" by locofungus · · Score: 1

      They can still prove that P = NP for specific cases

      This makes no sense at all. Everything in P is also in NP. Therefore every P problem is also an NP problem that can be solved in polynomial time - but that's nothing to do with proving "P=NP for specific cases"

      --
      God said, "div D = rho, div B = 0, curl E = -@B/@t, curl H = J + @D/@t," and there was light.
    10. Re: "While this is exciting news" by HornWumpus · · Score: 1

      Ass backwards.

      --
      John McAfee 'It was like that time I hired that Bangkok prostitute; to do my taxes, while I fucked my accountant'
    11. Re:"While this is exciting news" by Ungrounded+Lightning · · Score: 1

      What humanity doesn't have now is a way to write and compute NP algorithms.

      What humanity doesn't have now is a way to write and compute EFFICIENT NP algorithms.

      We can do NP just fine - by explicitly and separately computing the results for each of the possibilities at each step. But as the problem size gets larger the number of combinations explodes.

      That's why quantum computing is so desired: It can do all the possibilities in parallel in a single device, getting you down to polynomial time. But only for those problems where the exploding-combination steps can be reduced to something that maps to quantum operations - of which only a few are currently known. (Also: Getting a collection of qbits to stay in superposition for long enough to get the computation done and then to get the data out reliably is a real pain.)

      --
      Bantam Dominique roosters crow a four-note song. Once you've heard it as "Happy BIRTHday" you can't NOT hear it that way
    12. Re: "While this is exciting news" by slew · · Score: 1

      It only takes one specific example to disprove a general proposition.

      They can still prove that P = NP for specific cases, but if this proof holds up, the general case is disproven.

      This isn't interesting. We know of many algorithms that are both P and NP (e.g., can be solved deterministic polynomial time and by a non-determistic polynomial algorithm *and* verified in polynomial time). The interesting NP problems can be verified, but there is no known solution in polynomial time.

      If you could find an interesting problem in NP that didn't have a known solution in polynomial time (proving that it was in P), you would additionally have to prove it was not an NP-complete problem (otherwise all NP problems could be converted to your problem in polynomial time), because if it was an NP-complete problem and the proof holds, it would by definition not be in the set P. I suspect that proof would be as difficult as the P=NP problem.

      More interesting would be to find a problem that is was thought to be in NP, but it's complement (which would be in co-NP) is solvable in P time. That would be like finding the that NP != co-NP which would be much more interesting.

    13. Re: "While this is exciting news" by locofungus · · Score: 1

      Huh?

      Either a given NP problem is in P - in which case it's also a P problem, or it's not in P, in which case P!=NP.

      The two (obvious) routes to deciding P=NP is either to find an NP-complete problem that is also in P (proving P=NP) or finding an NP problem (doesn't need to be NP-complete in this case) that is not in P (proving that P!=NP)

      Factoring is in NP but not known whether it's in NP-complete - it would be very surprising if it were but it could be (last I knew) - but it's also not known to be in P - and that would raise some eyebrows too were it to be proved. But factoring could be proved to be in P without affecting the P=NP question.

      --
      God said, "div D = rho, div B = 0, curl E = -@B/@t, curl H = J + @D/@t," and there was light.
    14. Re: "While this is exciting news" by HornWumpus · · Score: 1

      Of course all P is NP, but this proves that not all NP is P.

      Disproving the general proposition.

      --
      John McAfee 'It was like that time I hired that Bangkok prostitute; to do my taxes, while I fucked my accountant'
    15. Re: "While this is exciting news" by 31415926535897 · · Score: 1

      I don't think so.

      One thing I recall from Combinatorial Algorithms was that all NP-complete problems were "essentially the same". What that meant was, if you had an NP-complete problem, you could transform it into another NP-complete problem. And what we spent way too much time doing was taking problems of unknown complexity and either trying to prove they were polynomial or transforming into an known NP-complete problem to prove that it too was NP-complete.

      What that means is that if you can prove that P=NP in one case, then you've proven it for all cases, and if you've proven that P!=NP in one case, then you've proven it for all cases.

      Scanning the paper, it looks like they took an NP-complete problem they were familiar with (Monotone Boolean Networks) and proved that for this particular algorithm, they have deduced that it's P!=NP by using bounds analysis. That generalizes, then, to P!=NP for all problems in the space. That is "Corollary 1" on page 36 in their paper, which is Turing Award worthy if true. I can't look at their paper and say whether or not what they did was correct, unfortunately, but their final step is sound.

    16. Re: "While this is exciting news" by locofungus · · Score: 1

      Factoring is in NP

      OK, I got a bit careless there. You really need to talk about decision problems. But the decision problem does N have a factor = k can trivially be converted to an algorithm to factor using a binary search.

      --
      God said, "div D = rho, div B = 0, curl E = -@B/@t, curl H = J + @D/@t," and there was light.
    17. Re: "While this is exciting news" by locofungus · · Score: 1

      Grrr

      Does N have a factor <= k

      --
      God said, "div D = rho, div B = 0, curl E = -@B/@t, curl H = J + @D/@t," and there was light.
    18. Re:"While this is exciting news" by Bob+the+Super+Hamste · · Score: 2

      Not really. A quantum computer isn't one that makes NP problems as easy as P problems even if it does offer a massive speedup as they are not believed to be non-deterministic Turing machines. For example the cracking of private key crypto systems a quantum computer does offer a massive speedup but it doesn't move the difficulty from NP to P. So instead of the runtime being O(2^n) on a classical computer the runtime is O(2^(n/2)) on a quantum computer. Now while this is an impressive speed gain, we move from stellar mass energy levels to total annual energy consumption of large powerful nation states, it doesn't mean that it breaks symmetric key crypto, only that we should double the key space to push things back up to stellar mass energy levels.

      --
      Time to offend someone
    19. Re:"While this is exciting news" by sexconker · · Score: 1

      Evidence that P = NP (or one is a subset of the other) means all cryptography is doomed to fail.

      No it wouldn't.

      f(x) = 0 will securely encrypt anything you throw at it, and that's not even O(n) complexity.

      Oh, you want reversible encryption? One time pads are perfect, and they scale linearly.

      P = NP just means that there's a polynomial equation to get the same solution set for a given exponential (or worse) equation. (And equation here can refer to a simple equation or a complex and iterative program, which itself is still an equation as long as its deterministic.)

      Evidence of P = NP doesn't make it true, nor does it give us an actual solution for a given NP problem, nor does it mean the polynomial solution will be faster than the non-polynomial one (there may be some insane coefficient on it that makes the NP solution better for all practical use).

      Cryptography is all about keeping a secret. Today we do that on-demand with key exchange algorithms. If all key exchange algorithms are trivial to break, we'll go back to pre-shared keys or one time pads. Both options are much more secure than using an insecure channel to establish a secure channel, regardless of your algorithm or how ephemeral your keys are.

      The problem is that they're unwieldy. You'll want to update your keys/pads regularly, perhaps even for each message. This means generating lots in advance and agreeing on a method to cycle through them, or it means using a secure channel frequently to generate new ones. There's no revocation mechanism, so you'll need a secure channel whenever shit goes down. For a secure channel, the best option is to meet in person, verify the other party, and generate and exchange keys/pads. You'll also need to store these securely.

      Cryptography will survive P=NP if that ever pans out (it won't).

    20. Re:"While this is exciting news" by sexconker · · Score: 1

      If P = NP then P * N ^ 100 = P * N ^ 99 = P

      P = 0, N = ?
      N = 1, P = ?

    21. Re:"While this is exciting news" by Jason1729 · · Score: 1

      We can solve NP problems by converting them to very inefficient deterministic problems and using deterministic algorithms. An NP algorithm would solve it in a nondeterministic way.

      Factoring a large number by dividing by every prime up to its square root is a deterministic algorithm even though factoring is an NP problem

      When you talking about computing all possibilities in parallel, you totally misunderstand quantum mechanics, that is not how quantum physics works, and we don't know yet how it works. For example, under the Many-Worlds Interpretation what you said *sort of* makes sense. Under the Copenhagen Interpretation, it's nonsense. And all these interpretations are just abstractions for things nobody understands.

    22. Re:"While this is exciting news" by EndlessNameless · · Score: 1

      I assume you're talking about asymmetric encryption. (Correctly used) OTP already gives perfect security symmetric encryption.

      Irrelevant. Roughly 99.999% of the way we use symmetric encryption is not compatible with OTPs.

      Mentioning OTPs in a conversation about real-world crypto makes me wonder if you understand the matter at all. I intend to ignore the rest of your post, and I suggest others do so as well. It is better to wait for real experts to weigh in.

      --

      ---
      According to the latest ruleset, this post should be modded as Vorpal Flamebait +5.
    23. Re:"While this is exciting news" by hord · · Score: 1

      If P = NP that implies that *all* problems of at least NP complexity are equivalent to P complexity. This implies that we should be able to solve *any* NP problem with a P solution. That's what the debate is about and why many people have for years now thought that P != NP. The intuition says that NP must be a harder complexity class and P is a sub-set within it otherwise we would be seeing general solutions for NP-hard problems that run in P time. The solutions to NP-hard problems we have today that approach this are very specialized corner-case NP problems. This would be another benefit to actually proving P != NP. We would be able to more accurately categorize higher level complexity beyond P into the other classes you mentioned as well as domain-specific sub-classes.

    24. Re: "While this is exciting news" by mr_mischief · · Score: 2

      There's more to NP than NP-complete. NP is the set of problems that can be solved in polynomial time on a nondeterministic system. P is the set of problems that can be solved in polynomial time on a deterministic system. NP-complete are problems that currently our best solutions are NP but the output of those problems can be checked for correctness as P. NP-complete problems all seem to be mappable to one another. That's not necessarily the case for all of NP.

      Proving NP-complete = P would only prove that subset, and NP != P is still a possibility.

      And then, of course, there's !P which is another class of problems altogether.

      Proving NP-complete != P would be exciting. Proving NP-complete = P would be more exciting. Proving NP != P would be very exciting. Proving NP = P would be world-changing.

    25. Re:"While this is exciting news" by HornWumpus · · Score: 1

      I don't think you understand the discussion...maybe I'm missing a joke.

      --
      John McAfee 'It was like that time I hired that Bangkok prostitute; to do my taxes, while I fucked my accountant'
    26. Re:"While this is exciting news" by zifn4b · · Score: 1

      Since P != NP is the expected answer, is this news really that exciting? Evidence that P = NP is the one that would actually be exciting, since it would suggest the existence of an unknown algorithm that handles certain problems far more efficiently than the currently known alternatives.

      Can you prove primes can't be factored in polynomial time? That is can you conclusively say that you've tried every logically possible algorithm to rule them all out? See, we're still where we always were on this question: we lack sufficient information to say one way or the other. Nothing really new here. Must be a slow news day on slashdot again.

      --
      We'll make great pets
    27. Re:"While this is exciting news" by cryptizard · · Score: 2
      Everyone is arguing with your second point but I will actually take issue with the first:

      The expected answer means we will have cryptographic security available indefinitely. We may have to keep switching algorithms, but in principle there will always be an algorithm out there that can't be quickly bypassed.

      That is actually not true. There is a very famous paper by Russell Impagliazzo titled A Personal View of Average-Case Complexity where he outlines five possible "worlds" we could be living in, hinged on the answer to some unknown questions. One of these is whether P = NP, but another is about average-case hardness (because P and NP are only defined for worst-case problems).

      The only world that is now no longer possible, if this new result is correct, is the first world Algorithmica where P = NP and every problem is essentially easy to solve. There are four other worlds that we could still be in, and I highly encourage you to read the paper to check them out, but one important point is that we could be in a situation where P != NP but the hard instances of problems are actually, in themselves, hard to find, i.e. average case problems are easy.

      This would preclude cryptography as we know it because it would be just as hard to encrypt something as it would be to break it. You could still encrypt if you are the government and you have billions of dollars of computers but it becomes effectively an arms race between attackers and defenders, and whoever spends more processing power wins.

      There is also the possibility that P != NP but one-way functions do not exist. That is, every function which can be efficiently computed in a forward direction can also be efficiently computed in the reverse direction. This would be the worst possibility because we would gain no new scientific advancement from fast algorithms to solve things like protein folding, circuit design, etc. and cryptography would also be impossible.

    28. Re:"While this is exciting news" by AmericaRunsOnDunkin · · Score: 1

      Evidence that P = NP (or one is a subset of the other) means all cryptography is doomed to fail.

      No it doesn't. Even if P = NP the conversion factors between algorithms can be so large that it's not possible in practice. I.e. x^100 is polynomial time, but not calculable on nearly on the same scale as x^2 or x^3.

      Some current cryptographic methods may fail, but probably not all. And new algorithms that don't rely on non-polynomial time calculations will be available (if they aren't already). I studied cryptography in grad school. Some of the details have slipped my memory but I'm positive this isn't the end of the world. Crypto will survive.

    29. Re:"While this is exciting news" by cryptizard · · Score: 1

      Another thing to consider is that we still don't know whether factoring, discrete logarithms, etc are even in NP in the first place

      Yes this is quite easily proven. Problems in NP can be efficiently verified and it is very easy to verify, if I give you two factors p and q, whether they multiply to a number n.

    30. Re:"While this is exciting news" by cryptizard · · Score: 1

      This is technically possible, but probably very unlikely. No natural problems are known which have a non-trivial lower bound of more than (I believe) \Omega(n^2). It seems that problems in higher polynomial classes are either very rare or we have yet to consider fields of math which would produce them.

    31. Re:"While this is exciting news" by nitehawk214 · · Score: 1

      NP does not mean "non polynomial". NP means "nondeterministic polynomial".

      --
      I'm a good cook. I'm a fantastic eater. - Steven Brust
    32. Re:"While this is exciting news" by jhol13 · · Score: 1

      No.
      We know there are problems which require exponential time (and/or space). No matter whether P == NP or not.
      There is no need for the cryptography to use NP problems.
      For example, prove a Presburger arithmetic problem. It will not happen "soon".

    33. Re:"While this is exciting news" by suutar · · Score: 1

      P is apparently known to be a subset of NP. We just don't know whether it's "less than" or "equal" yet.

    34. Re:"While this is exciting news" by cryptizard · · Score: 1

      x^100 is polynomial time, but not calculable on nearly on the same scale as x^2 or x^3

      It is true that there are problems with lower bounds of every possible polynomial (this follows from the time hierarchy theorem), there don't seem to be naturally occurring ones. I don't think there are any proven non-trivial lower bounds for a natural problem that are greater than n^2. Reductions are the same, most are done with very low polynomial complexity. So if a reduction proof was made that showed P = NP it would likely also lead to reasonably efficient algorithms for all problems in P.

      new algorithms that don't rely on non-polynomial time calculations will be available

      I'm not sure what you are imagining but this is kind of impossible, or at least not very friendly. If we start making encryption schemes that have only a polynomial separation between algorithms that perform the encryption and algorithms that break the encryption then we allow that expensive supercomputers will always be able to break encryption done by cheap, slow devices. This would be a dream for government surveillance.

    35. Re:"While this is exciting news" by cryptizard · · Score: 1

      That is only because factoring is not known to be (and probably isn't) NP-complete. If this result is true, and NP != P, then we do now know for sure that a large class of problems (NP-complete ones) do not have polynomial time algorithms.

    36. Re:"While this is exciting news" by TechyImmigrant · · Score: 1

      Since P != NP is the expected answer, is this news really that exciting? Evidence that P = NP is the one that would actually be exciting, since it would suggest the existence of an unknown algorithm that handles certain problems far more efficiently than the currently known alternatives.

      It's good news for crypto. If P != NP, then that means there isn't a polynomial time algorithm for breaking all crypto algorithms.

      --
      I should use this sig to advertise my book ISBN-13 : 978-1501515132.
    37. Re:"While this is exciting news" by TechyImmigrant · · Score: 1

      See here for all the quantum computational complexity classes:
      https://complexityzoo.uwaterlo...

      --
      I should use this sig to advertise my book ISBN-13 : 978-1501515132.
    38. Re:"While this is exciting news" by zifn4b · · Score: 1

      That is only because factoring is not known to be (and probably isn't) NP-complete.

      The best we can say is it is unknowable based on the information that we have today. We could attempt to try to calculate a probability about this but I'm fairly certain it wouldn't be accurate nor would it be useful. Let me pose a similar question, can you prove there is no diamond in my back yard? (borrowed from Sam Harris). It is similar to prove for the set of all possible algorithms that there exists 0 algorithms that could factor integers to determine whether they are prime in polynomial time. This is all about proving a negative.

      --
      We'll make great pets
    39. Re:"While this is exciting news" by cfalcon · · Score: 1

      > if I give you two factors p and q, whether they multiply to a number n

      Bear in mind that factoring is not known to be either P or NP.

    40. Re:"While this is exciting news" by cryptizard · · Score: 1

      lolwut? Is this a troll comment and I am just not getting it?

    41. Re:"While this is exciting news" by cryptizard · · Score: 1

      I used probably in a colloquial sense, like if god came down today and said at midnight he was going to tell us whether factoring is NP-complete I would bet money that it is not. There is no actual probability, it either is or isn't and we just don't know right now. I should have said it would be surprising if it was NP-complete. because that would imply NP = coNP which would be as surprising a result as P = NP.

    42. Re:"While this is exciting news" by epine · · Score: 1

      I don't think there are any proven non-trivial lower bounds for a natural problem that are greater than n^2.

      I suspect that if those n^2 reductions existed for all the as-yet unsolved problems, we would have figured out that P=NP long ago.

      It might just be that reductions with provable lower-bound n >> 2 are likewise >> hard to find.

      In which case your reasoning leads nowhere.

    43. Re:"While this is exciting news" by cryptizard · · Score: 1

      There also aren't any problems with known upper bounds that are very high, it is either we only know exponential algorithms or we know fairly efficient algorithms. There is no well-known problem that has like a O(n^10) as the best known algorithm.

    44. Re: "While this is exciting news" by slew · · Score: 1

      Not sure if you mis-worded something here but I don't quite follow. If you take any problem that you suspect is in NP and find a polynomial time algorithm for it is by definition then in P, and you've shed no light on the P=NP question. I think you're implying this point. So I'm interpreting what you've written as hypothesizing about showing some problem is neither in P nor NP-complete. This proof would be equivalent to proving P!=NP, as Ladner's Theorem proven in the 70s says that if there *are* any problems that exist strictly between P and NP-complete in so called NP-intermediate, then P!=NP. In other words it wouldn't just be as difficult as the P=NP problem, it *is* the P=NP problem.

      Yeah, that wasn't worded correctly. As I understand it, there might exist NP problems that are not NP-complete, but are also not P, but proving a specific problem is a so-called NP-intermediate does not seem to be the same as proving P!=NP. There might be a more straight forward proof which doesn't depend on identifying a NP-intermediate problem, and I suspect it would be as difficult as the P=NP problem.

    45. Re:"While this is exciting news" by russotto · · Score: 1

      There is no well-known problem that has like a O(n^10) as the best known algorithm.

      Primality testing is pretty close, at O(n^7.5) (where n is number of bits).

    46. Re:"While this is exciting news" by locofungus · · Score: 1

      I think it's careless wording - people using NP to mean the subset of NP that is not in P.

      Using this casual wording the question " Does P=NP?" becomes "Is NP empty?"

      Of course, NP (and P) are sets of decision problems so factoring itself isn't in either of them - although there are decision problems in NP that can be used to factor.

      --
      God said, "div D = rho, div B = 0, curl E = -@B/@t, curl H = J + @D/@t," and there was light.
    47. Re: "While this is exciting news" by locofungus · · Score: 1

      but proving a specific problem is a so-called NP-intermediate does not seem to be the same as proving P!=NP

      Huh? Of course it is!

      The question "Does P = NP?" says "Are all problems in NP also in P?" or, conversely, "Is there any problem in NP that is not in P?"

      Finding even one problem that is in NP but not in P is sufficient to decide P != NP.

      Because there are countless known NP-complete problems, if any problem (whether or not it was NP complete) was shown to be in NP but not in P then it would automatically follow that all NP-complete problems are also not in P.

      I think where you're getting confused is that showing a given NP problem (that is not NP complete) is actually in P doesn't tell you anything about P=NP. As one fairly recent example (15 years ago now I google it) - PRIMES was shown to be in P https://it.slashdot.org/story/...

      --
      God said, "div D = rho, div B = 0, curl E = -@B/@t, curl H = J + @D/@t," and there was light.
    48. Re:"While this is exciting news" by locofungus · · Score: 1

      Can you prove primes can't be factored in polynomial time?

      PRIMES is in P. The question is N prime can be decided in polynomial time. If the answer is yes (N prime) then it's prime factorization is trivially N.

      --
      God said, "div D = rho, div B = 0, curl E = -@B/@t, curl H = J + @D/@t," and there was light.
    49. Re:"While this is exciting news" by cryptizard · · Score: 1

      There are plenty of \Omega(n^3) algorithms.

      Care to name one?

    50. Re:"While this is exciting news" by cryptizard · · Score: 1

      Oh yes, this is definitely true. We can have the P != NP and cryptography is still impossible. Russel Impaggliazzo calls this possibility Pessiland in his famous five worlds paper.

    51. Re:"While this is exciting news" by ImprovOmega · · Score: 1

      Well, it is fairly easy to reduce factoring to an NP-complete problem (in P-time), but what you cannot do is reduce an NP-complete problem to factoring (that we know of at least). Thusly factoring has not been proven to be NP-complete. However if you can prove that P != NP-complete you're at least halfway there. If you could prove that P = NP-complete then factoring would be hopelessly broken.

    52. Re:"While this is exciting news" by cryptizard · · Score: 1

      Algorithms only prove an upper bound, not a lower bound. Big-Omega means lower bound.

    53. Re:"While this is exciting news" by Bengie · · Score: 1

      Quantum computers change symmetric key encryption from O(2^n) to O(2^(n/2)), saying nothing about the time take for each operation. But quantum computer can reverse certain types of private key crypto in the same number of operations as it takes to encrypt it, rendering those cryptos completely useless. Ignoring that currently adding more bits to a quantum computer is incredibly hard. Certain aspects of these algorithms could be scaled up to to where the quantum computer could not hold all of the state. RSA scales very poorly in size and people hate increasing the key size.

      There is working being done to create an asymmetric crypto that has no quantum weaknesses. I think Lattice encryption is one such.

    54. Re:"While this is exciting news" by david_thornley · · Score: 1

      And new algorithms that don't rely on non-polynomial time calculations will be available

      I'm not able to parse this.

      Encryption has to be efficient to be useful. That pretty much means P. That means that, if P=NP, decryption with known plaintext is efficient, and encryption is useless.

      --
      "When you have eliminated the unacceptable, whatever is left, however improbable, must be the truthiness" - Holmes
    55. Re:"While this is exciting news" by zifn4b · · Score: 1

      Well, it is fairly easy to reduce factoring to an NP-complete problem (in P-time), but what you cannot do is reduce an NP-complete problem to factoring (that we know of at least). Thusly factoring has not been proven to be NP-complete. However if you can prove that P != NP-complete you're at least halfway there. If you could prove that P = NP-complete then factoring would be hopelessly broken.

      Thank you for bringing some intelligence to this discussion. Cheers!

      --
      We'll make great pets
  3. Well duh... by Anonymous Coward · · Score: 1

    It has been a while since grad school, but I had always assumed this was the case (while understanding that it may never be proven). If P=NP then generally speaking all problems which are computationally expensive can be solved somewhat efficiently. P=NP would spell disaster for all manner of encryption-based security.

    I am willing to withdraw my comments if my age has decayed my thinking on this in the past 25 years.

    1. Re:Well duh... by Anonymous Coward · · Score: 3, Insightful

      Even if P were equal to NP it wouldn't mean the end of encyption based security. Most people forget P and NP are asymptotic complexity classes. No real world problem has ever had an instance whose input complexity tends to infinity.
      That's why Bubblesort (a sorry ass sorting algorithm) performs better than Quicksort or some other variant for small inputs. But you'd never guess that for the asymptotic complexity analysis.

    2. Re: Well duh... by p91paul · · Score: 1

      There is a couple of wrong points you are making: many problems are known to be non-polynomial regardless of the P=NP debate (NP does not stand for Not Polynomial, but for Nondeterministic Polynomial). Also, I'm not aware of any cryptographic algorithm which bases its security on P!=NP, so this discovery (or the contrary) would have no effect on cryptography.

    3. Re:Well duh... by ImprovOmega · · Score: 1

      If you could solve an NP-complete problem in P-time (thus proving that P = NP-complete), it would be the end of modern public key encryption protocols because you could factor out the private key in P-time. This is because factoring, being an NP problem (but not NP-complete, that we know of), is trivially reducible in P-time to an NP-complete algorithm and thus if P = NP-complete then factoring would be possible in P-time.

  4. Please mod parent up. by WindBourne · · Score: 1

    While p=np would have enabled a large number of interesting solutions, this is probably far more important to the world. So, please mod parent up.

    --
    I prefer the "u" in honour as it seems to be missing these days.
    1. Re:Please mod parent up. by ShanghaiBill · · Score: 1

      While p=np would have enabled a large number of interesting solutions

      Proving P=NP would mean a P solution to an NP problem was theoretically possible, but it wouldn't necessarily help you find one.

      Even if P!=NP, we might still be able to solve some NP problems in P time using quantum computing, although some people believe this is not true. Quantum computing can speed up NP algorithms but may not be able to get all the way to P.

      I didn't read the paper, but I skimmed the abstract. If this is really a proof that P!=NP, then Norbert deserves a Fields Medal. Alas, he appears to be over the 40 year age limit.

    2. Re:Please mod parent up. by cryptizard · · Score: 1

      Proving P=NP would mean a P solution to an NP problem was theoretically possible, but it wouldn't necessarily help you find one.

      Barring some very strange proof that would be fundamentally different from the way we currently know how to prove things in complexity that is exactly what it would mean. The proof would likely take the form of a reduction of some NP-complete problem to some problem in P, which would then, via a series of transformations, allow for all problems in NP to be solved in P time.

    3. Re:Please mod parent up. by cryptizard · · Score: 1

      I think "a large number of interesting solutions" is a bit of an understatement. It would mean that perfect unsupervised learning would be possible which would probably quickly usher in strong AI. I don't think we can even imagine what it would do to life on this planet if we had a reduction proof showing P = NP.

    4. Re: Please mod parent up. by hackwrench · · Score: 1

      Life is the only real np problem.We just like hearing the same stories being told over and over to different people

    5. Re:Please mod parent up. by crunchygranola · · Score: 1

      Proving P=NP would mean a P solution to an NP problem was theoretically possible, but it wouldn't necessarily help you find one.

      Barring some very strange proof that would be fundamentally different from the way we currently know how to prove things in complexity that is exactly what it would mean. The proof would likely take the form of a reduction of some NP-complete problem to some problem in P, which would then, via a series of transformations, allow for all problems in NP to be solved in P time.

      And that would be because what we are trying to prove here is nothing like the things we currently know to prove in complexity theory.

      Donald Knuth, the greatest living theoretical computer scientist thinks that P = NP, but that the proof we not help us find an algorithm (it would be non-constructive). He gives as an example of this type of proof the Robertson-Seymour Theorem proof that there exists a polynomial time algorithm to compute fixed-parameter tractability graph invariants of a particular type. But not only does it not indicate how to find such an algorithm, it shows that it will be extremely hard to find.

      The P+NP algorithm, if it exists, may be completely intractable in size or complexity, or time complexity, say X^Y for some colossal number Y (Graham's number exponent anyone?).

      --
      Second class citizen of the New Gilded Age
  5. Re:hate to brag... by tepples · · Score: 2

    This paper shows evidence that N != 1.

  6. Easy by stud9920 · · Score: 1

    If p was np then n could only be 1, p 0 or both. No such limitation is in the premises. Therefore p=np IN AN INFINITE MINORITY OF CASES.

  7. When will the cis-normativity end? by Anonymous Coward · · Score: 2, Funny

    Why do people obsess so much over whether a person has a P, doesn't have a P, or belongs to the set of people who have non-deterministic P times? Let people be themselves, and listen to them when they say they do not identify as the class that you first think! Sometimes life is more complex than it seems at first.

  8. Moderation fail. by Anonymous Coward · · Score: 1

    So much for the wisdom of the crowds. The post that speculates that "cryptography is doomed to fail" while getting wrong something as basic as the fact that P *is* a subset of NP gets quickly modded to 5, while your post and other interesting posts by people who have at least some idea of what they are conjecturing about linger in obscurity. (Not saying the dmgxmichael's post is bad per se, but it's not the 5 among this thread.)

  9. I've known this all along! by nickovs · · Score: 3, Funny

    I have discovered a truly marvelous proof of this, which this Slashdot comment is too narrow to contain.

    --
    If intelligent life is too complex to evolve on its own, who designed God?
  10. Hold your horses by l2718 · · Score: 4, Informative

    This is merely a preprint, not a published paper. In other words, this has not been referred – subjected to regular scientific scrutiny.

    Preprints are of great interest to researchers in the field -- they give them quick access to recent results before the slower process of scientific verification takes place. But preprints are not published papers (even those are not all correct!) – they aren't really useful to the general public. Especially in the case of major open problems like P=NP, such extraordinary claims require extraordinary verification, and this has yet to take place.

    The submission headline here is very misleading, as is the summary. Either this preprint is correct (extremely unlikely), and then it definitely shows that P!=NP, or the preprint if wrong (almost surely the case), at which point it's not clear that it contains enough correct and deep results to actually suggest anything about whether P=NP or not. A much better headline would have been "new arXiv preprint purports to prove that P!=NP", and a better summary would have been

    A recent arXiv preprint by Norbert Blum of the University of Bonn claims to show that P!=NP. This work has not been vetted by the general community and (as with every other claim of this type) is generally assumed to be incorrect. Readers who are not experts in complexity theory are advised to ignore this preprint until experts have had time to examine this work and its implications.

    1. Re:Hold your horses by fph+il+quozientatore · · Score: 1

      OTOH, this guy seems to be an expert in the field. If he claims to have proved it, then it's either correct or it has a very subtle flaw. One must be rather sure of yourself to go public with a claim like this one. So it's not like the false proofs that cranks keep publishing; this has the potential to be a serious thing. As a scientist working in a different field, I am very curious to hear about this.

      --
      My first program:

      Hell Segmentation fault

  11. P=NP vs PNP Is Dumb by Anonymous Coward · · Score: 1

    Different problems are different, some have P=NP solutions some do not have P=NP solutions. It depends on the problem and finding a universal P=NP solution is about equivalent to trying to win the game of life: there's no winning because there's no victory condition to begin with.

  12. Re:New Work Suggests ... by cryptizard · · Score: 1

    What word would you use to mean, "looks like it proves this but we really don't know yet because there might be a mistake in it and it will probably take months or years to decide if it is valid"?

  13. Basic Math by Khyber · · Score: 1

    "P=NP"

    Works when P=0 for any value of N. Works when N=1 for any value of P. So it IS equal, but only for a small percentage of possible cases. The summary makes it seem like it simply doesn't work in any case at all.

    --
    Still waiting on Serviscope_minor to wake up to fucking reality and realize that Jessica Price isn't going to fuck him.
  14. Re:Panda Bear Hamster by Anubis+IV · · Score: 1

    Yup. That's why I picked it as my analogy. I knew the counterexamples were well known.