A correspondence between the time and space complexity
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916536359321600 |
|---|---|
| author | Latkin, Ivan V. |
| author_facet | Latkin, Ivan V. |
| contents | We investigate the correspondence between the time and space recognition complexity of languages. For this purpose, we will code the long-continued computations of deterministic two-tape Turing machines by the relatively short-length quantified Boolean formulae. The modified Meyer and Stockmeyer method will appreciably be used for this simulation. It will be proved using this modeling that the complexity classes Deterministic Exponential Time and Deterministic Polynomial Space coincide. It will also be proven that any language recognized in polynomial time can be recognized in almost logarithmic space. Furthermore, this allows us slightly to improve the early founded lower complexity bound of decidable theories that are nontrivial relative to some equivalence relation (this relation may be equality) -- each of these theories is consistent with the formula, which asserts that there are two non-equivalent elements.
Keywords: computational complexity, the coding of computations through formulae, exponential time, polynomial space, the lower complexity bound of the language recognition |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_01184 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A correspondence between the time and space complexity Latkin, Ivan V. Computational Complexity Logic in Computer Science Logic 68Q15 (Primary), 68Q17, 03D15, 03B70 (Secondary) F.1.1; F.1.3; F.2.3; F.4.1; F.4.2; F.4.3 We investigate the correspondence between the time and space recognition complexity of languages. For this purpose, we will code the long-continued computations of deterministic two-tape Turing machines by the relatively short-length quantified Boolean formulae. The modified Meyer and Stockmeyer method will appreciably be used for this simulation. It will be proved using this modeling that the complexity classes Deterministic Exponential Time and Deterministic Polynomial Space coincide. It will also be proven that any language recognized in polynomial time can be recognized in almost logarithmic space. Furthermore, this allows us slightly to improve the early founded lower complexity bound of decidable theories that are nontrivial relative to some equivalence relation (this relation may be equality) -- each of these theories is consistent with the formula, which asserts that there are two non-equivalent elements. Keywords: computational complexity, the coding of computations through formulae, exponential time, polynomial space, the lower complexity bound of the language recognition |
| title | A correspondence between the time and space complexity |
| topic | Computational Complexity Logic in Computer Science Logic 68Q15 (Primary), 68Q17, 03D15, 03B70 (Secondary) F.1.1; F.1.3; F.2.3; F.4.1; F.4.2; F.4.3 |
| url | https://arxiv.org/abs/2311.01184 |