[FOM] Foundational Challenge

Lew Gordeew lew.gordeew at uni-tuebingen.de
Thu Aug 20 10:02:34 EDT 2020


Zitat von Thomas Klimpel <jacques.gentzen at gmail.com>:

> Lew Gordeew wrote:
>> Peer-reviewed proof of NP = PSPACE is already available
>>
>> http://dx.doi.org/10.18778/0138-0680.2020.16
>> https://czasopisma.uni.lodz.pl/bulletin/article/view/8169
>>
>> (Warning: it's hard proof theory)
>
> What happened to the LEAN formalization that Edward Hermann Haeusler
> wanted to finish first
> (https://cs.nyu.edu/pipermail/fom/2019-July/021620.html), before
> publishing (yet another incomplete version of) this article?

Please ask E. H. Haeusler, not me. As far as I know he tried to work  
out a different proof idea. Apparently it took more time than expected.

> What
> happened since https://arxiv.org/abs/1907.03858, on which this new
> proof is based according to the abstract, and where he did not appear
> as co-author?

So we decided to elaborate and submit my proof that was already  
finished. The current paper upgrades our first joint paper, so he  
naturally appears as co-author too.

> Why did neither of you ever update https://arxiv.org/abs/1609.09562,
> even so your subsequent publications clearly show that you accept that
> this version contains a serious mistake?

It was not a peer-reviewed publication and the mistake was technical  
rather than serious in my opinion. A complete upgrade is in both  
https://arxiv.org/abs/1907.03858 and current publication  
http://dx.doi.org/10.18778/0138-0680.2020.16.

> A peer-reviewed article is certainly a nice achievement, but it
> shouldn't be overstated in the context of ambitious proofs.

Sure. See paper's Editorial remark. "The subeditor dealing with this  
paper (Peter Schroeder-
Heister) and the two reviewers were not able to check proofs in all  
detail and therefore
cannot fully con
firm their correctness. However, in view of the  
importance of the results
claimed and the originality of the logical proof methods employed, and  
in accordance
with the aim of the journal as a forum for the wide dissemination of  
original results
by rapid publication, they agree that the paper should be available to  
the scienti
c
community in published form to enable further discussion."

> A link to
> a funny reference with many examples was given in
> (https://www.scottaaronson.com/blog/?p=3409#comment-1743482): "This
> P!=NP paper from 2017
> (http://cris.teiep.gr/jspui/bitstream/123456789/1482/1/The_3rdClay_version1_Conference.pdf)
> contains a nice reference section of P vs NP proofs which actually
> managed to get published in some seemingly serious journals, like IEEE
> Latin America Transactions."

I don't care about funny references with regard to P vs NP. Our NP vs  
PSPACE paper is based on serious Proof Theory and further discussion  
in question (see above) should follow this pattern.

LG




More information about the FOM mailing list