[FOM] Gordeev and NP = PSPACE again
Lew Gordeew
lew.gordeew at uni-tuebingen.de
Tue Jul 30 01:26:10 EDT 2019
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
More information about the FOM
mailing list