Slashdot Mirror
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.
And all these years we've been using PnP computer hardware and PNP transistors.
#DeleteFacebook
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 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.
Hate to brag but I could have told you that straight of the bat. If you look closely at P=NP you'll see there's an additional N on the right side of the equation, making them not the same.
I thought P=NP wasn't possible unless an external element was influencing things.
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.
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.
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.
Of course P != NP... one side has an extra N in it. Duh. Isn't it plainly obvious?
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.)
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?
Every time this silly little conjecture comes up, I chuckle a little bit. I solved it with two friends in a weekend back in 1982 but I rather enjoy watching the world squirm over it. We swore ourselves to secrecy, except that the first person to die will release it with their last will and testament as part of their estate.
It's actually kind of a sick game. The first of the three of us to die gets credit for solving the problem. Haha..
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
Obviously:
N = PN
a) for every P if N=0
b) for every N if P=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.
Picture of a non-brown hamster.
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.
What does all this really mean? /. and not Nature or something..
Why is this on
It would probably just make it impossible to prove that some problems are hard to solve (and stop trying to solve them efficiently in the general case, or use the facts in a crypto context) by proving that they're NP-complete.
Reminder: there's a long list of known NP-complete problems, which are problems that would show P=NP if they were proven to be polynomially solvable. So when you try to come up with an efficient algorithm to solve some task T but can't even come up with some poly time algorithm, you want to try and see if you could reduce in poly time some known NP-complete problem A to your task T (meaning that for any instance of A you can work things around until you just have to solve a poly number of T problems to get the answer of this instance of A). If you can, congratulations, you've just proved that T is NP-complete, so perhaps you can publish, or you can only get back to the thing you want to do and try another approach, like figure out if there's any additional properties in the instances of T you'd get in your context and use them to solve the damn thing, or see if you can at least find a solution that's not worse than 2 times the optimal one, etc.
P=NP would make all that meaningless. Quite a number of scientific papers would instantly become toilet papers.
But it would probably NOT give you practical algorithms for any of those NP-complete problems, even if there's a constructive proof with a concrete well-understood algorithm, because there's a high chance a proof would come with a high-degree polynomial and/or very high constants.
I know of an algorithm that's linear time. Except that the linear constant in the theoretical algorithm is a tower of exponentials. The Universe would be far too small to run these thousand lines of code, and would be dead long before the compile-time constants have been computed. You couldn't even fit one pointer in the Universe.
So no, P=NP would not doom crypto. It would make things harder to prove, but proofs are already quite shaky anyway. So what if your crypto problem is NP-complete? Not all instances are hard. It wouldn't be surprising if 99% of the instances are solvable in linear time, while you don't even want 0.001% of your encrypted things cracked.
Corn and salt is actually what they give to concentration camp inmates in the DPRK.
Doritos is death camp food lol.
Are you looking for professional graphics designer to create your company, photography pages or brand logo. Do you like caricature or vector arts? Dont know what to do? Then, contact with me to help to create these. Contact me: https://goo.gl/hdZizG
> New Work Suggests ...
This is math that we're talking about here. There is no "suggest"-ing. It's either a valid proof, or it's not. There's no grey area at all.
"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.
So we still have no reason to believe that P = NP and even if it is true we don't have the 'one algorithm to rule them all' that would allow us to solve all the NP problems in P-TIME.
At the end of the day, life still goes on as usual:
- researchers will continue to strive for the Holy Grail of Computer Science ('The One Algorithm to Rule Them All")
- researchers will continue to investigate heuristics to give reasonable solutions to NP problems in reasonable time
- at some point in the future it MAY be determined (as some findings purport that it is undecidable/unsolvable)
All is as it should be; we would like to know if P = NP from a theoretical standpoint while practically speaking we need algorithms to solve problems we have now.
Corn distills well. Corn liquor... Nfm
Fuck evidence, there's plenty of evidence that P != NP. Wake me up when you prove something.
You imagine a _practical_ reduction of NP to P. Meaning low enough constants/degree that large enough instances can be run in low enough time for some useful NP-complete problems. This hypothesis is much stronger than just P=NP. In that case, yes, it would be a game changer, though probably not that much for most life forms on the planet.
If we had efficient algorithms for protein folding or circuit design, wouldn't we make progress in medicine or power saving etc.?
Also, this doesn't impact crypto based on quantum entanglement, right?
https://www.quora.com/Whats-the-status-of-Norbert-Blums-claim-that-operatorname-P-neq-operatorname-NP/answer/Alon-Amit
Dude you work in a call center sending out emails with no-reply
I don't even know why you're commenting on computer science articles.