Back to Search Start Over

On Lev Gordeev's 'On P Versus NP'

Authors :
Narváez, David
Phillips, Patrick
Publication Year :
2021

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 $\neq$ 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.<br />Comment: This article has 6 pages and 1 figure. This work as supported in part by NSF grant CCF-2030859 to the Computing Research Association for the CIFellows Project and by NSF grant CCF-2006496

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2104.07166
Document Type :
Working Paper