Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916059539308544 |
|---|---|
| author | Lin, Tianrong |
| author_facet | Lin, Tianrong |
| contents | We prove in this paper that there is a language $L_s$ accepted by some nondeterministic Turing machine that runs within time $O(n^k)$ for any positive integer $k\in\mathbb{N}_1$ but not by any ${\rm co}\mathcal{NP}$ machines. Then we further show that $L_s$ is in $\mathcal{NP}$, thus proving a groundbreaking result that $$\mathcal{NP}\neq{\rm co}\mathcal{NP}. $$
The main techniques used in this paper are simulation and the novel new techniques developed in the author's recent work. Our main result has profound implications, such as $\mathcal{P}\neq\mathcal{NP}$, etc. Further, if there exists some oracle $A$ such that $\mathcal{P}^A\ne\mathcal{NP}^A={\rm co}\mathcal{NP}^A$, we then explore what mystery lies behind it and show that if $\mathcal{P}^A\ne\mathcal{NP}^A={\rm co}\mathcal{NP}^A$ and under some rational assumptions, then the set of all ${\rm co}\mathcal{NP}^A$ machines is not enumerable, thus showing that the simulation techniques are not applicable for the first half of the whole step to separate $\mathcal{NP}^A$ from ${\rm co}\mathcal{NP}^A$. Finally, a lower bounds result for Frege proof systems is presented (i.e., no Frege proof systems can be polynomially bounded). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_10476 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines Lin, Tianrong Computational Complexity 68Q15, 03F20 We prove in this paper that there is a language $L_s$ accepted by some nondeterministic Turing machine that runs within time $O(n^k)$ for any positive integer $k\in\mathbb{N}_1$ but not by any ${\rm co}\mathcal{NP}$ machines. Then we further show that $L_s$ is in $\mathcal{NP}$, thus proving a groundbreaking result that $$\mathcal{NP}\neq{\rm co}\mathcal{NP}. $$ The main techniques used in this paper are simulation and the novel new techniques developed in the author's recent work. Our main result has profound implications, such as $\mathcal{P}\neq\mathcal{NP}$, etc. Further, if there exists some oracle $A$ such that $\mathcal{P}^A\ne\mathcal{NP}^A={\rm co}\mathcal{NP}^A$, we then explore what mystery lies behind it and show that if $\mathcal{P}^A\ne\mathcal{NP}^A={\rm co}\mathcal{NP}^A$ and under some rational assumptions, then the set of all ${\rm co}\mathcal{NP}^A$ machines is not enumerable, thus showing that the simulation techniques are not applicable for the first half of the whole step to separate $\mathcal{NP}^A$ from ${\rm co}\mathcal{NP}^A$. Finally, a lower bounds result for Frege proof systems is presented (i.e., no Frege proof systems can be polynomially bounded). |
| title | Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines |
| topic | Computational Complexity 68Q15, 03F20 |
| url | https://arxiv.org/abs/2406.10476 |