On $NP$ versus $\rm coNP$ and Frege Systems
<|reference_start|>On $NP$ versus $\rm coNP$ and Frege Systems: We prove in this paper that there is a language $L_d$ accepted by some nondeterministic Turing machines but not by any ${\rm co}\mathcal{NP}$-machines (defined later). Then we further show that $L_d$ is in $\mathcal{NP}$, thus proving that $\mathcal{NP}\neq{\rm co}\mathcal{NP}$. The techniques used in this paper are lazy-diagonalization and the novel new technique developed in author's recent work \cite{Lin21}. Since there exists oracle $A$ such that $\mathcal{NP}^A={\rm co}\mathcal{NP}^A$, we then explore what mysterious behind it and showing that if $\mathcal{NP}^A={\rm co}\mathcal{NP}^A$ and under some rational assumptions, the set of all polynomial-time co-nondeterministic oracle Turing machines with oracle $A$ is not enumerable. As a by-product, we reach the important result that $\mathcal{P}\neq\mathcal{NP}$ \cite{Lin21} once again, which is clear from the above outcome and the well-known fact that $\mathcal{P}={\rm co}\mathcal{P}$. Next, we show that the complexity class ${\rm co}\mathcal{NP}$ has intermediate languages, i.e., there are language $L_{inter}\in{\rm co}\mathcal{NP}$ which is not in $\mathcal{P}$ and not ${\rm co}\mathcal{NP}$-complete. We also summarize other direct consequences implied by our main outcome such as $\mathcal{NEXP}\neq{\rm co}\mathcal{NEXP}$ and other which is in the area of proof complexity. Lastly, we show a lower bounds result for Frege proof systems, i.e., no Frege proof systems can be polynomial bounded.<|reference_end|>
@article{lin2024on,
    title={On $NP$ versus ${\rm co}NP$ and Frege Systems},
    author={Tianrong Lin},
    journal={arXiv preprint arXiv:2406.10476},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.10476},
    primaryClass={cs.CC}
}