Some Observations on Infinitary Complexity
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2018
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918508285132800 |
|---|---|
| author | Carl, Merlin |
| author_facet | Carl, Merlin |
| contents | Continuing the study of complexity theory of Koepke's Ordinal Turing Machines (OTMs) that was started by Rin, Löwe and the author, we prove the following results:
(1) An analogue of Ladner's theorem for OTMs holds: That is, there are languages $\mathcal{L}$ which are NP$^{\infty}$, but neither P$^{\infty}$ nor NP$^{\infty}$-complete. This answers an open question of \cite{CLR}.
(2) The speedup theorem for Turing machines, which allows us to bring down the computation time and space usage of a Turing machine program down by an aribtrary positive factor under relatively mild side conditions by expanding the working alphabet does not hold for OTMs.
(3) We show that, for $α<β$ such that $α$ is the halting time of some OTM-program, there are decision problems that are OTM-decidable in time bounded by $|w|^β\cdotγ$ for some $γ\in\text{On}$, but not in time bounded by $|w|^α\cdotγ$ for any $γ\in\text{On}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1801_10027 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Some Observations on Infinitary Complexity Carl, Merlin Logic Continuing the study of complexity theory of Koepke's Ordinal Turing Machines (OTMs) that was started by Rin, Löwe and the author, we prove the following results: (1) An analogue of Ladner's theorem for OTMs holds: That is, there are languages $\mathcal{L}$ which are NP$^{\infty}$, but neither P$^{\infty}$ nor NP$^{\infty}$-complete. This answers an open question of \cite{CLR}. (2) The speedup theorem for Turing machines, which allows us to bring down the computation time and space usage of a Turing machine program down by an aribtrary positive factor under relatively mild side conditions by expanding the working alphabet does not hold for OTMs. (3) We show that, for $α<β$ such that $α$ is the halting time of some OTM-program, there are decision problems that are OTM-decidable in time bounded by $|w|^β\cdotγ$ for some $γ\in\text{On}$, but not in time bounded by $|w|^α\cdotγ$ for any $γ\in\text{On}$. |
| title | Some Observations on Infinitary Complexity |
| topic | Logic |
| url | https://arxiv.org/abs/1801.10027 |