Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Math

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

Posted by msmash 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.
This discussion has been archived. No new comments can be posted.

New Work Suggests That P Is Not Equal To NP More

New Work Suggests That P Is Not Equal To NP

Comments Filter:

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

  • "While this is exciting news" (Score:4, Informative)

    by Stormy Dragon ( 800799 ) on Wednesday August 16, 2017 @10:27AM (#55025451)

    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.

    • Re:"While this is exciting news" (Score:5, Insightful)

      by dmgxmichael ( 1219692 ) on Wednesday August 16, 2017 @10:39AM (#55025575) Homepage
      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.
      • 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.

        • 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 [wikipedia.org]. Quantum computing can speed up NP algorithms [wikipedia.org] 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

          • 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.

            • 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 [wikipedia.org] that there exists a polynomial time algorithm to compute fixed-parameter tractability graph invariants of a particular type. But

          • Life is the only real np problem.We just like hearing the same stories being told over and over to different people
        • 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.

      • Re: (Score:2)

        by Rei ( 128717 )

        Well, at least we'll find out the answer eventually [blogspot.com]. ;)

      • Re:"While this is exciting news" (Score:5, Informative)

        by Stormy Dragon ( 800799 ) on Wednesday August 16, 2017 @10:59AM (#55025791)

        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.

        • Moderation fail. (Score:1)

          by Anonymous Coward

          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.)

      • 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 m

        • 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.

      • 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 tru

      • 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 poss

      • 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

        • 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 su

          • Re: (Score:2)

            by epine ( 68316 )

            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.

            • 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.

              • 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).

        • 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.

      • Re: (Score:1)

        by jhol13 ( 1087781 )

        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".

      • Re: (Score:2)

        by suutar ( 1860506 )

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

    • Re: (Score:2)

      by zifn4b ( 1040588 )

      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.

      • 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.

        • Re: (Score:2)

          by zifn4b ( 1040588 )

          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. Thi

          • 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.
            • 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.

              • Re: (Score:2)

                by zifn4b ( 1040588 )

                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!

      • 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.

    • 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.

  • Well duh... (Score:1)

    by Anonymous Coward

    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.

    • Re: (Score:3, Insightful)

      by Anonymous Coward

      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.

      • 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.
    • 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.

  • 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.

  • When will the cis-normativity end? (Score:2, Funny)

    by Anonymous Coward

    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.

  • I've known this all along! (Score:4, Funny)

    by nickovs ( 115935 ) on Wednesday August 16, 2017 @11:42AM (#55026353)

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

  • Hold your horses (Score:5, Informative)

    by l2718 ( 514756 ) on Wednesday August 16, 2017 @11:57AM (#55026549)

    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.

    • 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.

  • P=NP vs PNP Is Dumb (Score:1)

    by Anonymous Coward

    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.

  • "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.

Slashdot Top Deals

Every nonzero finite dimensional inner product space has an orthonormal basis. It makes sense, when you don't think about it.

Close