This work is licensed under a
Creative Commons License.
|
Thursday, September 24, 2009
My two cents on P vs NP
Posted by GASARCH
There have been several posts on blogs about P vs NP and two expository articles. Is there anything else to add. I'm not sure, but here are my 2 cents.
- QUESTION: If it is shown that P &ne NP then how will this affect the real world? ANSWER: The solution will give great insight into computation and thus will ultimately help the real world of algorithms. QUESTION: How do you know this? ANSWER: Um...
- QUESTION: If you were told that P vs NP was REALLY SOLVED yesterday and asked to bet which way it went, how would you bet? I would bet P=NP. I actually believe that P&ne NP; however, my believe in the paucity of current techniques for showing P &ne NP is greater than my believe that P&ne NP.
12:26 PM
# 11 comments
-
I love the first Question and its Answer.
-
For Q2, if P vs NP was solved, and it was known to be solved then it must have been P≠NP; only a fool would tell people if they found P=NP.
-
Golly ... the subtlety of argument (2) compels admiration ... it is an argument that I for one have *never* heard before.
-
actually luigi finally resolved the problem.
http://arxiv.org/ftp/arxiv/papers/0909/0909.3868.pdf
-
Second argument is incomplete. We also need to know how hard a proof for P=NP supposing P=NP was true.
-
why would you be a fool to say you found P=NP?
-
More "will P vs NP be solved" posts? This is getting a bit old ...
-
" mario said...
actually luigi finally resolved the problem.
http://arxiv.org/ftp/arxiv/papers/0909/0909.3868.pdf"
Someone proved that P=NP in 9 pages? Hmm...
if anyone can be bothered reading through this, tell us how he made a mistake :P
-
luigi made no mistake. the most profound comment in his proof of P=NP was "having spent over 2 years to achieve this there are no
complicated ideas or sophisticated development will, if I'm right how can this result
has been hidden for so long?"
and i ask you, the reader, how could it have been deprived of us? finally, the long lasting conjecture (of all times) has been resolved.
I think we should conclude all these posts by thanking the author for his breakthrough.
-
Perhaps this has already been addressed somewhere else in the blog, but after reading comments like #4 and #9 above, it would be great if the blog author(s) could comment on the proliferation of so-called proofs for the P vs. NP problem.
See, for example, the following webpage (http://www.win.tue.nl/~gwoegi/P-versus-NP.htm) for a number of different "proofs" that P=NP, or P/=NP, or that P vs. NP is undecidable.
Arguably most of this activity comes from individuals without very deep expertise in theoretical computer science and these proofs are very likely full of errors, but still, is anybody paying attention to this? Checking the proofs? Informing the masses (as well as the authors of these proofs)?
What is the TCS experts' view of all this activity?
-
luigi offers a new entry on the list of proof methods given on the site
http://school.maths.uwa.edu.au/~berwin/humour/invalid.proofs.html
.. proof by wikipedia..
seems to fall at some of the checks listed on
http://scottaaronson.com/blog/?p=304
Links to this post:
Weblog Home
Archives
