[agi] Re: [agi] P≠NP
Does anyone have any comments on this proof? I don't have the mathematical background to tell if it is correct. But it seems related to the idea from algorithmic information theory that the worst case complexity for any algorithm is equal to the average case for compressed inputs. Then to show that P != NP you would show that SAT (specifically 9-SAT) with compressed inputs has exponential average case complexity. That is not quite the approach the paper takes, probably because compression is not computable. -- Matt Mahoney, matmaho...@yahoo.com From: Kaj Sotala xue...@gmail.com To: agi agi@v2.listbox.com Sent: Thu, August 12, 2010 2:18:13 AM Subject: [agi] Re: [agi] P≠NP 2010/8/12 John G. Rose johnr...@polyplexic.com BTW here is the latest one: http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf See also: http://www.ugcs.caltech.edu/~stansife/pnp.html - brief summary of the proof Discussion about whether it's correct: http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p?np/ http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p≠np/ http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p≠np-proof/ http://news.ycombinator.com/item?id=1585850 Wiki page summarizing a lot of the discussion, as well as collecting many of the links above: http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper#Does_the_argument_prove_too_much.3F --- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?; Powered by Listbox: http://www.listbox.com * Open Link in New Tab * Download --- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?member_id=8660244id_secret=8660244-6e7fb59c Powered by Listbox: http://www.listbox.com
[agi] Re: [agi] P≠NP
2010/8/12 John G. Rose johnr...@polyplexic.com BTW here is the latest one: http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf See also: http://www.ugcs.caltech.edu/~stansife/pnp.html - brief summary of the proof Discussion about whether it's correct: http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p?np/ http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p≠np/ http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p≠np-proof/ http://news.ycombinator.com/item?id=1585850 Wiki page summarizing a lot of the discussion, as well as collecting many of the links above: http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper#Does_the_argument_prove_too_much.3F --- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?member_id=8660244id_secret=8660244-6e7fb59c Powered by Listbox: http://www.listbox.com
[agi] Re: [agi] P≠NP
This is a very powerful argument, but is not quite a rigorous proof. Thermodynamics is like saying that because all zeros below 10^20 have a real part of 0.5 therefore there are no non trivial zeros for which that is not the case. What I am saying is pedantic, very pedantic but will still affect Clay's view of the matter. You will *not* be able to decode Blackberry, of course. - Ian Parker 2010/8/12 John G. Rose johnr...@polyplexic.com BTW here is the latest one: http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf *agi* | Archives https://www.listbox.com/member/archive/303/=now https://www.listbox.com/member/archive/rss/303/ | Modifyhttps://www.listbox.com/member/?;Your Subscription http://www.listbox.com --- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?member_id=8660244id_secret=8660244-6e7fb59c Powered by Listbox: http://www.listbox.com
