FOM: news on unprovability of P=?NP vznuri at
Wed Sep 5 21:56:42 EDT 2001

hi all. just wanted to drop you a line on 
recent developments over on theory-edge.

dr.solovay weighed in with a review of the
paper that daCosta & Doria posted to theory-edge files section
looking at the unprovability of P=?NP in peano arithmetic..

> The main result claimed in the paper is that Peano
> Arithmetic [henceforth PA] does not prove the obvious formalization of
> "P != NP". If this result had been proved, it would have been one of
> the most important and significant results ever proved in either
> computer science or mathematical logic.
> However, the proof in the paper under discussion is
> erroneous. In my judgement, there is absolutely nothing of any
> scientific merit in the paper. No progress has been made on the
> understanding of the "P != NP" question and there is not the slightest
> likelihood that the methods of this paper will lead to any insight on
> this question.

RS's more general analysis of the line of attack in this msg

imho, from my peripheral vantage point of watching developments
on this 1sthand over about six months, RS is seriously 
mistaken on specific & general points..
although I am not convinced DC+FD have a bulletproof proof "yet".
my comments to that effect follow in the subsequent msgs on theory-edge.

feel free to drop by theory-edge for any upcoming developments..
the paper can be downloaded from yahoo by anyone curious..

More information about the FOM mailing list