New paper on P vs NP

[Lew Gordeew]

Hello dear fans of computational complexity,

enclosing a new paper on P vs NP

http://arxiv.org/abs/2005.00809

Abstract: 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 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.

All proofs (if correct) are elementary.

Regards,
LG