Prev: [M-R test] Formula for p(k,t)
Next: Scalable Key Cryptography - The Universal Model.
From: Pubkeybreaker on 9 Aug 2010 14:34
On Aug 9, 2:11 pm, g...(a)nope.ucsd.edu (Greg Rose) wrote:
> In article <1b2c15fd-73ad-47d2-b41d-3a428c79a...(a)d17g2000yqb.googlegroups..com>,
> Tom St Denis  <t...(a)iahu.ca> wrote:
>

> Not my field of expertise either, but the paper
> looks plausible.  However, it will still be a
> couple of years before enough people who are
> competent to examine it will be able to agree on
> whether the proof is correct or not.

I am reading it now. It is a serious effort. I will need to
do quite a bit of reading (of some of the references) to understand
the proof in detail, but from what I have read so far, the approach
seems to work.

Ask me again after my 4th or 5th reading.......
From: Pubkeybreaker on 9 Aug 2010 14:41
On Aug 9, 9:57 am, Simon Johnson <simon.john...(a)gmail.com> wrote:
> I am no expert in this field (or in any field for that matter :) ) but
> check this out:
>
> http://www.scribd.com/doc/35539144/pnp12pt
>
> If this paper's claims are true, the problem is solved. I think we're
> all agreed that this represents a significant breakthrough in the
> field of complexity theory.

It is a whole new approach. Deolalikar has tied P-time computations
into the statistical properties of large, random graphs (via
satisfiability). (first studied
extensively by Renyi and Paul Erdos). Notices of AMS had a recent
very nice survey paper on random graphs.
From: Paul Rubin on 9 Aug 2010 15:05
Pubkeybreaker <pubkeybreaker(a)aol.com> writes:
> I am reading it now. It is a serious effort. I will need to
> do quite a bit of reading (of some of the references) to understand
> the proof in detail, but from what I have read so far, the approach
> seems to work.
>
> Ask me again after my 4th or 5th reading.......

Have you looked at the comments on Richard Lipton's blog?

http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
From: unruh on 9 Aug 2010 15:27
On 2010-08-09, Paul Rubin <no.email(a)nospam.invalid> wrote:
> Pubkeybreaker <pubkeybreaker(a)aol.com> writes:
>> I am reading it now. It is a serious effort. I will need to
>> do quite a bit of reading (of some of the references) to understand
>> the proof in detail, but from what I have read so far, the approach
>> seems to work.
>>
>> Ask me again after my 4th or 5th reading.......
>
> Have you looked at the comments on Richard Lipton's blog?
>
> http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/

To summarize for those who have not read it
Maybe. Maybe not.
First  |  Prev  | 
Pages: 1 2
Prev: [M-R test] Formula for p(k,t)
Next: Scalable Key Cryptography - The Universal Model.