[FOM] Gordeev and NP = PSPACE again
Timothy Y. Chow
tchow at math.princeton.edu
Mon Jul 29 19:03:51 EDT 2019
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
More information about the FOM
mailing list