New paper on P vs NP
Lew Gordeew
lew.gordeew at uni-tuebingen.de
Wed Jan 6 12:15:08 EST 2021
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)
More information about the FOM
mailing list