# [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

http://www.ugcs.caltech.edu/~stansife/pnp.html - brief summary of the proof

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://news.ycombinator.com/item?id=1585850

Wiki page summarizing a lot of the discussion, as well as collecting

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
https://www.listbox.com/member/?&;

* Open Link in New Tab