New Work Suggests That P Is Not Equal To NP (arxiv.org) 147
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.
Wow (Score:2)
And all these years we've been using PnP computer hardware and PNP transistors.
Re: (Score:2)
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.
Re: (Score:2)
That statement is so "dope". ba dum tish.
"While this is exciting news" (Score:4, 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.
Re:"While this is exciting news" (Score:5, Insightful)
Please mod parent up. (Score:2)
Re: (Score:2)
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
Re: (Score:2)
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.
Re: (Score:2)
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
Re: Please mod parent up. (Score:1)
Re: (Score:2)
Re: (Score:2)
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 ap
Re: (Score:2)
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.
Re: (Score:2)
> 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.
Re: (Score:2)
Re: (Score:2)
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.
Re: (Score:2)
Re: (Score:2)
Well, at least we'll find out the answer eventually [blogspot.com]. ;)
Re:"While this is exciting news" (Score:5, Informative)
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).
Exciting news is obviously not always good news.
Moderation fail. (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.)
Re: (Score:2)
If P = NP then P * N ^ 100 = P * N ^ 99 = P
Re: (Score:2)
If P = NP then P * N ^ 100 = P * N ^ 99 = P
P = 0, N = ?
N = 1, P = ?
Re: (Score:2)
I don't think you understand the discussion...maybe I'm missing a joke.
Re: (Score:2)
Re: (Score:2)
There are plenty of \Omega(n^3) algorithms.
Care to name one?
Re: (Score:2)
Re: (Score:2)
NP does not mean "non polynomial". NP means "nondeterministic polynomial".
Re: (Score:3)
I assume you're talking about asymmetric encryption. (Correctly used) OTP already gives perfect security symmetric encryption.
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
Re: (Score:2)
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.
Re: (Score:2)
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
Re: (Score:3)
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
Re: (Score:1)
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
Re: (Score:2)
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)
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.
Re: (Score:2)
Re: (Score:2)
Primality testing is pretty close, at O(n^7.5) (where n is number of bits).
Re: (Score:2)
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)
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)
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: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.
Re: (Score:2)
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
Re: (Score:3)
Re: (Score:2)
See here for all the quantum computational complexity classes:
https://complexityzoo.uwaterlo... [uwaterloo.ca]
Re: (Score:2)
Re: (Score:2)
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.
Re: (Score:3)
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 ha
Re: (Score:2)
Yup. That's why I picked it as my analogy. I knew the counterexamples were well known.
Re: "While this is exciting news" (Score:4, 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.
Re: (Score:2)
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"
Re: (Score:2)
Ass backwards.
Re: (Score:2)
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 - an
Re: (Score:2)
Of course all P is NP, but this proves that not all NP is P.
Disproving the general proposition.
Re: (Score:2)
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.
Re: (Score:2)
Grrr
Does N have a factor <= k
Re: (Score:2)
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 (otherwis
Re: (Score:2)
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.
Re: (Score:2)
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
Re: (Score:2)
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
Re: (Score:3)
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 su
Re: (Score:2)
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.
Re: (Score:2)
Re: (Score:2)
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
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
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!
Re: (Score:2)
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.
Re: (Score:2)
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)
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)
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: (Score:2)
Re: Well duh... (Score:1)
Re: (Score:3)
This paper shows evidence that N != 1.
Easy (Score:2)
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)
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)
I have discovered a truly marvelous proof of this, which this Slashdot comment is too narrow to contain.
Hold your horses (Score:5, 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
Re: (Score:2)
P=NP vs PNP Is Dumb (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.
Basic Math (Score:2)
"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.
Re: (Score:1)
ffs where do they all come from
a dorito is literally some flat corn with dyed garlic salt on it
how are these so many calories
this is a true pnp problem, not like this worthless paper
Corn is what we feed to pigs and cows to fatten them up on the cheap.
The only thing in the world that actually fully digests it is the termite.
Corn is a trash crop.
Re: (Score:2)