تقرير
On $NP$ versus ${\rm co}NP$
| العنوان: | On $NP$ versus ${\rm co}NP$ |
|---|---|
| المؤلفون: | Lin, Tianrong |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computational Complexity, 68Q15, 03F20 |
| الوصف: | 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). 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}. As a by-product, we reach the important result \cite{Lin21} that $\mathcal{P}\neq\mathcal{NP}$ once again, which is clear from the above outcome and the well-known fact that $\mathcal{P}={\rm co}\mathcal{P}$. Then, we show that the complexity class ${\rm co}\mathcal{NP}$ has intermediate languages. Other direct consequences are also summarized. Comment: [v2] initial version; 22 pages; 2 figures; section 6 added; comments are welcome. arXiv admin note: text overlap with arXiv:2110.06211 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2406.10476 |
| رقم الأكسشن: | edsarx.2406.10476 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |