On Lev Gordeev's "On P Versus NP"

[Lew Gordeew]

In fact I had withdrawn that paper from arXiv (cf. Attachment) already  
on Feb 15 2021 with my own Comment:

"Upper bounds on negative deviations in section 3.1.2 are wrong due to  
errernous calculation".

Alas, that proof included technical mistakes. However I don't give up  
the roadmap yet. A modified version is being elaborated and  
step-by-step verified by Isabelle.

Best,
LG
------------------------------------------------------------------------------
Attachment:

Your withdrawal of 2005.00809 by submission submit/3605411 has
been published and is available at:

arXiv:2005.00809
From: Lev Gordeev <lew.gordeew at uni-tuebingen.de>
Date: Sat, 2 May 2020 12:03:50 GMT   (25kb)
Date (revised v2): Fri, 31 Jul 2020 05:19:05 GMT   (28kb)
Date (revised v3): Fri, 25 Dec 2020 16:02:21 GMT   (35kb)
Date (revised v4): Mon, 15 Feb 2021 09:23:54 GMT   (0kb,I)

Title: On P Versus NP
Authors: Lev Gordeev
Categories: cs.CC
Comments: Upper bounds on negative deviations in section 3.1.2 are  
wrong due to
   errernous calculation

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

   I generalize a well-known result that P = NP fails for monotone polynomial
circuits - more precisely, that the clique problem CLIQUE(k^4,k) is not
solvable by Boolean (AND,OR)-circuits of the size polynomial in k. In  
the other
words, there is no Boolean (AND,OR)-formula F expressing that a given graph
with k^4 vertices contains a clique of k elements, provided that the circuit
length of F, cl(F), is polynomial in k. In fact, for any solution F in
question, cl(F) must be exponential in k. Moreover this holds also for  
DeMorgan
normal (abbr.: DMN) (AND,OR)-formulas F that allow negated variables. Based on
the latter observation I consider an arbitrary (AND,OR,NOT)-formula F and
recall that standard NOT-conversions to DMN at most double its circuit length.
Hence for any Boolean solution F of CLIQUE(k^4,k), cl(F) is  
exponential in k. I
conclude that CLIQUE(k^4,k) is not solvable by polynomial-size Boolean
circuits, and hence P is not NP. The entire proof is formalizable by standard
methods in the exponential function arithmetic EFA.

------------------------------------------------------------------------------

Zitat von "Timothy Y. Chow" <tchow at math.princeton.edu>:

> 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


-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: Text
URL: </pipermail/fom/attachments/20210421/645860e7/attachment-0001.ksh>