On Lev Gordeev's "On P Versus NP"
Timothy Y. Chow
tchow at math.princeton.edu
Mon Apr 19 12:29:19 EDT 2021
FOM readers may recall that Lew Gordeew announced a "New paper on P vs NP"
back in December 2020.
https://cs.nyu.edu/pipermail/fom/2020-December/022429.html
David Narváez and Patrick Phillips have recently posted a preprint to the
arXiv with the following abstract.
In the paper "On P versus NP," Lev Gordeev attempts to extend the method
of approximation, which successfully proved exponential lower bounds for
monotone circuits, to the case of De Morgan Normal (DMN) circuits. As in
Razborov's proof of exponential lower bounds for monotone circuits,
Gordeev's work is focused on the NP-complete problem CLIQUE. If
successful in proving exponential DMN circuit lower bounds for CLIQUE,
Gordeev would prove that P ≠ NP. However, we show that Gordeev makes a
crucial mistake in Lemma 12. This mistake comes from only approximating
operations over positive circuit inputs. Furthermore, we argue that
efforts to extend the method of approximation to DMN circuits will need
to approximate negated inputs as well.
https://arxiv.org/abs/2104.07166
Tim
More information about the FOM
mailing list