[FOM] Gordeev and NP = PSPACE again

Edward Hermann Haeusler edward.haeusler at gmail.com
Wed Jul 31 19:50:38 EDT 2019

```Thank you for the question!
Yes, we have followed different approaches. It is a long history.

All the

On Wed, Jul 31, 2019 at 8:19 PM Joe Shipman <joeshipman at aol.com> wrote:

> That is a welcome development. Is your completion of the proof independent
> of his? Or do you use some of the new constructions in his new preprint?
>
> — JS
>
> Sent from my iPhone
>
> On Jul 31, 2019, at 1:53 AM, Edward Hermann Haeusler <
> edward.haeusler at gmail.com> wrote:
>
> Dear Timothy,
>
> As prof. Gordeev knows, we took slightly different directions in order to
> proof our result. In order to avoid incomplete versions, I and my students,
> are formalizing  our version in LEAN. Only after each relevant part is
> formalized and checked there will be an article published it in arxiv......
>
> Best regards,
>
> Hermann
>
>
>
> Em ter, 30 de jul de 2019 às 7:02 PM, Lew Gordeew <
> lew.gordeew at uni-tuebingen.de> escreveu:
>
>> Dear Tim,
>>
>> It's easy. Proof outline shown in preprint [2] turned out to be
>> incomplete, although we stand by its general roadmap. First verified
>> part of [2] was published in an authorized paper [3]. Second, final
>> part is elaborated in my new preprint [1] (hopefully it is complete
>> and correct). By the way, it is the abstract of [1] (not [2]) that
>> says "We upgrade [3] to a complete proof of the conjecture NP =
>> PSPACE." Thus "[1] does not cite [2], but cites only [3]."
>>
>> Best regards,
>> Lev
>>
>>
>> Zitat von "Timothy Y. Chow" <tchow at math.princeton.edu>:
>>
>> > Lev Gordeev has recently posted an arXiv preprint purporting to
>> > prove that NP = PSPACE.
>> >
>> >   [1]  Lev Gordeev, Proof Compression and NP Versus PSPACE, Part 2,
>> >        https://arxiv.org/abs/1907.03858
>> >
>> > FOM readers may recall that Gordeev and Haeusler posted an arXiv
>> > preprint back in 2016, also claiming to give a proof that NP = PSPACE.
>> >
>> >   [2]  Lew Gordeev and Edward Hermann Haeusler, NP vs PSPACE,
>> >        https://arxiv.org/abs/1609.09562
>> >
>> > There was some discussion of [2] on FOM back in October 2016:
>> >
>> >
>> > To summarize the discussion, some people pointed out that what
>> > Gordeev and Haeusler were claiming in [2] seemed to contradict known
>> > results, but Gordeev and Haeusler replied that in fact there was no
>> > contradiction. Also, Richard Zach said that several crucial points
>> > in [2] were unclear.
>> >
>> > In addition, there was an amusing interchange on Scott Aaronson's
>> > blog, where he gave 500:1 odds against [2] being correct, betting
>> > with someone using the pseudonym "Polymath."  Polymath said, "I'm
>> > sure the correctness of their proof will be settled one way or
>> > another within 2 or 3 months," but I have no idea whether Polymath
>> > and Aaronson actually settled their bet.
>> >
>> > https://www.scottaaronson.com/blog/?p=2925
>> >
>> > Skimming [1] briefly, I was surprised to find that [1] makes no
>> > mention of [2].  Instead, [1] refers to a recently published paper
>> > by Gordeev and Haeusler:
>> >
>> >   [3] L. Gordeev and E. H. Haeusler, Proof Compression and NP Versus
>> >       PSPACE, Studia Logica 107 (2019), 55-83.
>> >
>> > [3] does not claim to prove that NP = PSPACE.  The abstract of [2]
>> > says, "We upgrade [3] to a complete proof of the conjecture NP =
>> > PSPACE."
>> >
>> > Since [2] has not been withdrawn from the arXiv, one might suppose
>> > that the authors stand by its correctness, but in that case it is
>> > curious that
>> >
>> > a. the published paper [3], whose abstract and content superficially
>> > look a lot like [2], conspicuously avoids claiming to prove that NP
>> > = PSPACE, and
>> >
>> > b. as already mentioned, [1] does not cite [2], but cites only [3].
>> >
>> > Note also that [1] is authored only by Gordeev and not by Haeusler.
>> >
>> > I believe that Gordeev and Haeusler subscribe to FOM, so perhaps
>> > they can clarify whether they still maintain that [2] provides a
>> > complete and correct proof that NP = PSPACE.
>> >
>> > Tim
>> > _______________________________________________
>> > FOM mailing list
>> > FOM at cs.nyu.edu
>> > https://cs.nyu.edu/mailman/listinfo/fom
>>
>>
>>
>> _______________________________________________
>> FOM mailing list
>> FOM at cs.nyu.edu
>> https://cs.nyu.edu/mailman/listinfo/fom
>>
>> --
> Edward Hermann Haeusler
> Associate Professor
> Department of Informatics
> PUC-Rio
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> https://cs.nyu.edu/mailman/listinfo/fom
>
>

--
Edward Hermann Haeusler
Associate Professor
Department of Informatics
PUC-Rio
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20190731/7c3a2bfd/attachment-0001.html>
```