New manuscripi on NP $\neq$ co=NP

[martdowd at aol.com]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20220305/0f36f8dc/attachment.html>