If's its legit proof, they author should be able to explain why SAT2 is in P and SAT3 is NP-complete. That's my BS test.
A Solution of the P versus NP Problem?
51–60 of 303 posts
Re: A Solution of the P versus NP Problem?
#52Scott 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
FWIW, my assessment is that this paper passes the Aaronson test, as well as my own personal bogometer. If I were a betting man, my money would be on "the proof will turn out to have a flaw, but it will be hard to find the flaw, and the finding of the flaw will be interesting in and of itself, and possibly even advance the field."
Re: A Solution of the P versus NP Problem?
#53Just a half minute skim shows the author claims it passes the natural proof barrier but makes no claim about it being non-relativizing or non-algebraizing.
For those following along at home: this is important because we have a proof that relativizing wouldn't work. In this context, relativizing means relative to an oracle. For example, P^A means "just like a Turing machine would regularly recognize languages except this one has a magical oracle that can recognize A in one step". A can be arbitrarily complex, including NP-complete ones like 3SAT. This is important becaus…
I first learned about this because there's a decades-old joke in NetHack that cites this result when you ask for a major consultation from the Oracle when you can't afford to pay for it. I think the joke is that in this case, the Oracle can't tell you anything that's useful to you. :-)
Re: A Solution of the P versus NP Problem?
#54Can someone ELI5 what this problem is, how likely the proof is to hold up to scrutiny, and whether P != NP follows?
Here's a great video on the subject:
https://www.youtube.com/watch?v=YX40hbAHx3s
Re: A Solution of the P versus NP Problem?
#55Can someone ELI5 what this problem is, how likely the proof is to hold up to scrutiny, and whether P != NP follows?
Scott Aaronson has done some really good write-ups about P-NP, including what it means and what avenues of proof are possible. I'd start here: http://www.scottaaronson.com/papers/pnp.pdf . It probably doesn't count as "ELI5", but it's something.
That's a paper worth reading even if you don't understand it all because it will give you a good feeling for the magnitude of the problem. But it's actually surprisingly accessible. Aaronson is quite good at making hard things (relatively) easy to understand.
Re: A Solution of the P versus NP Problem?
#56What are the implications of solving the P versus NP problem? What practical effects would that have? Not trying to belittle the problem, just curious as an outsider.
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…
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.
Re: A Solution of the P versus NP Problem?
#57Scott 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
Points number 6 and 10 may apply. I only skimmed the paper and may have missed the really interesting point, but to me the argument and method just looks too simple to have been missed by everyone for all the time. But I am also totally not an expert in the field.
Re: A Solution of the P versus NP Problem?
#58I like the straightforward title. I know that it is politically correct to christen your paper solving e.g. the Poincare conjecture like e.g. "Ricci flow with surgery on three-manifolds", but all rules are there to be broken once.
I wish the author best of luck.
Re: A Solution of the P versus NP Problem?
#59I like the straightforward title. I know that it is politically correct to christen your paper solving e.g. the Poincare conjecture like e.g. "Ricci flow with surgery on three-manifolds", but all rules are there to be broken once. I wish the author best of luck.
At least he couldn't resist making the important point a corollary.
Re: A Solution of the P versus NP Problem?
#60Earlier quoted context omitted.
>Nobody's really interested in a proof that P != NP. I doubt that.
> I doubt that. Let me clarify: Nobody appeared to be interested in funding a graduate student to prove P != NP.
Your clarification makes sense - a PhD advisor with a bit of NSF or other grant money would likely only fund a grad student to work on a problem that has a reasonable likelihood of generating some concrete, positive, and publishable results. This typically means an incremental result on a problem of interest to the research community.
That having been said, an accepted proof that P != NP would result in a Turing award and an additional $1M for solving one of the seven Millenium Prizes. This has been an open problem for decades, and it is a problem of enormous importance and visibility.