Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909630562566144 |
|---|---|
| author | Lin, Tianrong |
| author_facet | Lin, Tianrong |
| contents | The {\em diagonalization technique} was invented by Georg Cantor to show that there are more real numbers than algebraic numbers and is very crucial in {\em theoretical computer science}. In this work, we enumerate all of the polynomial-time deterministic Turing machines and diagonalize against all of them by a universal nondeterministic Turing machine. As a result, we obtain that there is a language $L_d$ not accepted by any polynomial-time deterministic Turing machines but accepted by a nondeterministic Turing machine running within time $O(n^k)$ for any $k\in\mathbb{N}_1$. Based on these, we further show that $L_d\in\mathcal{NP}$. That is, in this work, we present a proof that $\mathcal{P}$ and $\mathcal{NP}$ differ. Meanwhile, we show that there exists a language $L_s$ in $\mathcal{P}$, but the machine accepting it also runs within time $O(n^k)$ for all $k\in\mathbb{N}_1$. Lastly, we show that if $\mathcal{P}^O=\mathcal{NP}^O$ and on some rational base assumptions, then the set $P^O$ of all polynomial-time deterministic oracle Turing machines with oracle $O$ is not enumerable, thus demonstrating that the diagonalization technique ({\em via a universal nondeterministic oracle Turing machine}) will generally {\em not} apply to the relativized versions of the $\mathcal{P}$ versus $\mathcal{NP}$ problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_06211 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines Lin, Tianrong Computational Complexity Formal Languages and Automata Theory 68Q15, 68Q17 The {\em diagonalization technique} was invented by Georg Cantor to show that there are more real numbers than algebraic numbers and is very crucial in {\em theoretical computer science}. In this work, we enumerate all of the polynomial-time deterministic Turing machines and diagonalize against all of them by a universal nondeterministic Turing machine. As a result, we obtain that there is a language $L_d$ not accepted by any polynomial-time deterministic Turing machines but accepted by a nondeterministic Turing machine running within time $O(n^k)$ for any $k\in\mathbb{N}_1$. Based on these, we further show that $L_d\in\mathcal{NP}$. That is, in this work, we present a proof that $\mathcal{P}$ and $\mathcal{NP}$ differ. Meanwhile, we show that there exists a language $L_s$ in $\mathcal{P}$, but the machine accepting it also runs within time $O(n^k)$ for all $k\in\mathbb{N}_1$. Lastly, we show that if $\mathcal{P}^O=\mathcal{NP}^O$ and on some rational base assumptions, then the set $P^O$ of all polynomial-time deterministic oracle Turing machines with oracle $O$ is not enumerable, thus demonstrating that the diagonalization technique ({\em via a universal nondeterministic oracle Turing machine}) will generally {\em not} apply to the relativized versions of the $\mathcal{P}$ versus $\mathcal{NP}$ problem. |
| title | Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines |
| topic | Computational Complexity Formal Languages and Automata Theory 68Q15, 68Q17 |
| url | https://arxiv.org/abs/2110.06211 |