81–90 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
" Yet here’s the bloodied patient, and here we are in the emergency room. " " The lemma encrusted shoulders of giants. " Aaronson on writes very well.
What 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 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, either, until another member of the TCS community can vouch for it. There have been many serious-looking attempts at PvNP that turn out to have fundamental flaws.
Earlier quoted context omitted.
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."
After overlooking the paper and applying Scott Aaronson's criterion I bet against you and bet: - The proof will turn out to have a flaw - The flaw will not be that hard to find (though probably not completely trivial; but rather of the kind: it takes much time to go to the details of the proof arguments) - The flaw will not be interesting in itself and will not advance the field
Earlier quoted context omitted.
" Yet here’s the bloodied patient, and here we are in the emergency room. " " The lemma encrusted shoulders of giants. " Aaronson on writes very well.
A little too flowery. He's also needlessly political.
However the author missed that there is a special case for N == 1, where actually P == NP (sorry, I could not resist).
Earlier quoted context omitted.
On your second point, a construction which transforms NP-complete problems into P problems in polynomial time necessarily implies P = NP, by construction. If the algorithm isn't correct, then it's a heuristic, not an algorithm, and we have piles of heuristics for working with NP-complete problems already.
I'm pretty far out of my area of expertise, so I'll take your word for it. Could an an algorithm be correct, but not proven correct, or is it defined as a heuristic at that point?
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.
It is my understanding that P = NP might have serious implications for quantum physics (ie, quantum physics suggests that P shouldn't be equal to NP).
It's interesting because it mix two interesting topics, that are well known in the popular science forums, but are very technical and most people don't want to read all technical the details of both.
Relevant xkcd: https://xkcd.com/1240/