[FOM] Gordeev and NP = PSPACE again

Edward Hermann Haeusler edward.haeusler at gmail.com
Wed Jul 31 01:53:00 EDT 2019


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:
> >
> >   https://cs.nyu.edu/pipermail/fom/2016-October/thread.html
> >
> > 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20190731/84594ef3/attachment.html>


More information about the FOM mailing list