171–180 of 303 posts
Scott Aaronson on "suppose someone sends you a complicated solution to a famous decades-old math problem, like P vs. NP. How can you decide, in ten minutes or less, whether the solution is worth reading?": http://www.scottaaronson.com/blog/?p=304
So there's your real answer.
Interesting that this is the second P!=NP proof from a University of Bonn researcher. Other one, by Mathias Hauptmann, is here: https://arxiv.org/abs/1602.04781 I never did hear the status of Hauptmann's proof (I'm not connected to academia so only know what I've read on the internet), but given it's been over a year without word, presumably there's something flawed. I might not get too excited over this proof, eithe…
Sigma_2^p != NP as far as I know and after a brief skimming the paper does not mention P != NP.
Edit: the paper does indeed mention P != NP in the form of P != Sigma_2^p => P != Sigma_1^p = NP. Please disregard my comment.
Interesting that this is the second P!=NP proof from a University of Bonn researcher. Other one, by Mathias Hauptmann, is here: https://arxiv.org/abs/1602.04781 I never did hear the status of Hauptmann's proof (I'm not connected to academia so only know what I've read on the internet), but given it's been over a year without word, presumably there's something flawed. I might not get too excited over this proof, eithe…
How does the paper of Hauptmann prove P != NP? Sigma_2^p != NP as far as I know and after a brief skimming the paper does not mention P != NP. Edit: the paper does indeed mention P != NP in the form of P != Sigma_2^p => P != Sigma_1^p = NP. Please disregard my comment.
This is probably why there is not a proof yet, since the truth is undesirable.
Earlier quoted context omitted.
Seconded. The flaws in these papers are not hard to find. They usually amount to misunderstanding of definitions or the results they cite.
Unlikely considering the author of the paper. I'm basing that on other comments on the thread which this section seems to be missing, e.g.: > ...this guy is an established senior researcher at the University of Bonn
Earlier quoted context omitted.
If only we had a way to make finding the flaw as easy as verifying the flaw
I don't think it would be possible to make finding it as easy as verifying it, but how can we prove that?
Earlier quoted context omitted.
Are you one of those people who equates any mention whatsoever of Trump as "being needlessly political"?
Not at all. But bringing him up in an unrelated post on a technical blog just screams "virtue signaling" to me.
You know that was an interesting and useful concept before you guys decided to turn into yet another empty insult to fling at people.
Earlier quoted context omitted.
I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.
Actually, we already know an algorithm that solves an NP complete problem in polynomial time iff P = NP. We can just enumerate all programs and ask them to generate witnesses. As we can decide whether a witness is valid and there is a program that always outputs a valid witness if P=NP, we can find that program within finite steps and the algorithm is correct.
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.
Say what? A lot of work is based on the assumption that P!=NP so you have to be clever in other ways.