New paper on P vs NP

[Lew Gordeew]

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

> Lew Gordeew wrote:
>
>> No, I don't see how to seriously weaken EFA. Sorry.
>
> Exactly what part of the proof requires going beyond S_2^2?

I use the ordinary exponentiation x -> 2^x in order to arrive at the  
required upper bounds as in Theorem 13. This function is hardly  
formalizable in S_2^2. Actually it is *not* formalizable there by  
S_2^2 = S_2^1 (that follows from our claim NP = coNP [GH2], [GH3])  
together with P != EXP and Buss' polynomial-time characterization of  
S_2^1.

> Alternatively, what makes your property non-natural in the sense of  
> Razborov and Rudich?

I did not discuss that concept.

> You say that your proof does not introduce "new groundbreaking  
> ideas" and analyzes "already known techniques in a more  
> sophisticated Boolean framework."  But if your property is  
> non-naturalizable then that is certainly groundbreaking.

In 1--3, p. 2, I made comparison to standard monotone approach (B) and  
failed attempts to expand it onto circuits with negative inputs using  
symmetric approximations (cf. references [7], [11], [12]). Here  
"symmetric" means that the approximations should symultaneously  
preserve moderate deviations in both positive and negative domains. In  
contrast, my "asymmetric" approximations don't care about negative  
deviations. This weakening is compensated in Section 3.1.4 by an  
appropriate CLIQUE-related Boolean approach that was not considered in  
previous papers on P vs NP. Still, I would not call it groundbreaking.

In an earlier draft I proved the main result with respect to a  
modified NP-complete version of CLIQUE problem that admits symmetric  
approximations. However that proof was technically more complicated  
and I switched to the current easier verifiable version.

[GH2] L. Gordeev, E. H. Haeusler, Proof Compression and NP Versus  
PSPACE II, Bulletin of the Section of Logic (49) (3): 213--230 (2020)
http://dx.doi.org/10.18788/0138-0680.2020.16

[GH3] L. Gordeev, E. H. Haeusler, Proof Compression and NP Versus  
PSPACE II: Addendum,
http://arxiv.org/abs/2011.09262 (2020) (submitted to BSL)