[FOM] Gordeev and NP = PSPACE again

[Joe Shipman]

I’m Polymath and I owe Aaronson $20 because although G&H’s approach may lead to a proof eventually, the 2016 preprint as it stood was insufficient. H told me in 2018 they were continuing to work on it and had not given up. I am pretty sure there is no issue of contradicting known results.

— JS 

Sent from my iPhone

> On Jul 29, 2019, at 7:03 PM, Timothy Y. Chow <tchow at math.princeton.edu> wrote:
> 
> 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