New manuscripi on NP $\neq$ co=NP

[Lew Gordeew]

Dear Martin,

I am confused about your manuscript. For in Description you wrote  
"Here, a much simpler method is considered , which yields a remarkably  
simple proof that NP = co-NP", whereas your Abstract says "Here, a  
much simpler method is considered , which yields a remarkably simple  
proof that NP ≠ co-NP". Which statement is correct?

Let me mention that even stronger equalities NP = co-NPNP = PSPACE  
have been already proved and published:
[1] L. Gordeev, E. H. Haeusler, "Proof Compression and NP Versus  
PSPACE II", Bulletin of the Section of Logic (49) (3): 213–230 (2020),
[2] L. Gordeev, E. H. Haeusler, "Proof Compression and NP Versus  
PSPACE II: Addendum", Bulletin of the Section of Logic (51), 9 pp.  
(2022), Published online: January 07, 2022;  
http://dx.doi.org/10.18788/0138-0680.2022.01.

Since our basic paper [1] uses complex proof theoretic methods, we  
also elaborated an easy overview:
"On proof theory in computational complexity: overview",  
https://arxiv.org/abs/2201.04118.

Best wishes,
LG

> FOM:
>
> After my bungled earlier attempt, I think I finally have a proof that
> NP$\neq$co-NP.  A preprint is available at
>  Separating some Complexity Classes
>  https://www.researchgate.net/publication/359037590
>
> I sent it to someone for checking on 2/23, but I haven't heard back so
> I'm posting it.  If any FOM readers find a problem please send me an email.
> I've submitted it to the JACM, but I can withdraw it.  I can also delete it
> from ResearchGate.
>
> Abstract:
> In \cite{DoGD} a ``universal representing formula function'' was defined,
> and consideration given to whether it could be used to construct
> a ``self-referential'' propositional formulas.
> Here, a much simpler method is considered,
> which yields a remarkably simple proof that $\NP\neq\cNP$.
> The method  generalizes to yield that the
> classes of the P hierarchy are not closed under complementation,
> and NEXP is not closed under complementation.
>
> I also have an outline of a proof of Cook's conjecture; I'll write it
> up before too long.
>
> Let $D_{\EF,k}$ denote the term $D$ of theorem 4 of [DoSS] for $P=\EF$.
> Let $\isD(d,j)$ be true iff $d=D_{\EF,|j|}$.
> Let $\dIsTaut$ be $\isD(d,j)\Ra\Tru(d,y)=1$.
> The following may be shown:
> 1) The representing formulas of $\dIsTaut$ do not have polynomially bounded
>    $\EF$ proofs.
> 2) $\dIsTaut$ is provable in $\LE_2$A (double exponential arithmetic).
> 3) Consequently, $\dIsTaut$ is provable from $\Con_{\LA}$ in $\LA$
>    (theorem 84 of [DoEQ]).
> 4) Consequently, the representing formulas of $\dIsTaut$ have polynomial
>    length $\EF$ derivations from the representing formulas of $\Con_{\LA}$
>    (Corollary IV.3.3 of [DoTH]).
> 5) Consequently, the representing formulas of $\Con_{\LA}$ do not have
>    polynomial length $\EF$ proofs.
>
> [DoSS]  https://www.researchgate.net/publication/359037590
> [DoEQ]  https://www.researchgate.net/publication/350500125
> [DoTH]  http://hdl.handle.net/1807/73092
>
>
> Martin Dowd