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

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.

Comments

"While this is exciting news"

[Stormy Dragon]

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"

[dmgxmichael]

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.

Re:"While this is exciting news"

[Stormy Dragon]

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.

Re:"While this is exciting news"

[locofungus]

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

Re: "While this is exciting news"

[Anubis IV]

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.

Re: "While this is exciting news"

[HornWumpus]

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.

Re:"While this is exciting news"

[Bob the Super Hamste]

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.

Re: "While this is exciting news"

[mr_mischief]

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.

Re:"While this is exciting news"

[cryptizard]

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.

Re:Well duh...

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

Re:hate to brag...

[tepples]

This paper shows evidence that N != 1.

When will the cis-normativity end?

[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!

[nickovs]

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

Hold your horses

[l2718]

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.