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=8660244&id_secret=8660244-6e7fb59c Powered by Listbox: http://www.listbox.com
