181–190 of 303 posts
If p != np, then comp sci will lose much of its appeal. There is an underlying hope behind the field that p = np, otherwise most problems of interest are intractable, and programmers are no longer masters of the universe. This is probably why there is not a proof yet, since the truth is undesirable.
Earlier quoted context omitted.
Here is a largely correct ELI5: P != NP asks the question "Are problems that are easy to verify (NP) also Easy to solve ? (P)". Note that the reverse is obviously true : problems that are easy to solve are also easy to verify . Here is an example: Take the problem "Find minimum of 5,6,7,8". You solve the problem and tell me that the answer is 5. I can verify your answer by solving the problem myself, getting the the…
Also wanted to say: People have been taking a go at this for many years now. Grapevine says that several large CS departments in many countries have groups of graduate students devoted to solving sub-problems of the entire proof because it is a prestige issue. Extraordinary claims require extraordinary proof and any proof will go through multiple peer reviews. Perelman's proof of Poincare Conjecture was studied for s…
Almost everybody in the field knows we're far from an actual proof with current techniques.
Earlier quoted context omitted.
The most interesting thing is if P=NP. If that's the case, that means that there is an algorithm that can solve any NP problem in polynomial time. This means that things like crypto would be able to be cracked in polynomial time which presents a huge problem for security. We basically operate under the assumption that P!=NP currently. Validation that this is true doesn't really change much. I can't speak to how this…
Would it present a problem for cryptography though? Quadratic algorithms are seen as already slow, cubic algorithms as unbearable garbage you best try to avoid if your data size is not tiny. And this completely ignores constant factors that can play a big role. Homomorphic encryption for instance fails to be usable just on a huge constant factor.
I would normally sigh and move on seeing such a claim, but this guy is an established senior researcher at the University of Bonn. A career-ending disaster or instant and eternal fame, that's some serious cahunas.
It shouldn't be career ending unless there's been malfeasance or some kind of sloppy work. The people who go down hard usually have some crime beyond audacity. It could easily cause some painful embarrassment, but hopefully that would pass with time. Maybe embarrassment similar to that faced by researchers who's results suggested FTL communication, but it turned out to be a bad fiber-optic cable. I didn't follow up b…
A list of 116 previous "solutions" to the P versus NP problem: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
A list of 116 previous "solutions" to the P versus NP problem: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
After skimming its interesting that the majority of the proofs in your list claim P equals NP. I would have guessed it would be more common for proofs to claim the opposite because P != NP makes sense intuitively. That being said it would certainly be more exciting if P did equal NP.
Earlier quoted context omitted.
After skimming its interesting that the majority of the proofs in your list claim P equals NP. I would have guessed it would be more common for proofs to claim the opposite because P != NP makes sense intuitively. That being said it would certainly be more exciting if P did equal NP.
A simple but wrong proof of "P = NP" is easier to write in some ways, since you "just" need to provide a single algorithm for one NP-hard problem, and show that it runs in polynomial time. It looks like many or most of the proof attempts in that list take this form. A plausible proof of "P != NP" won't be quite as simple to express, since it needs to prove that all such algorithms do not run in polynomial time.
Please forgive me if my liberal use of the language is an offense
If p != np, then comp sci will lose much of its appeal. There is an underlying hope behind the field that p = np, otherwise most problems of interest are intractable, and programmers are no longer masters of the universe. This is probably why there is not a proof yet, since the truth is undesirable.