Back to Search Start Over

A correspondence between the time and space complexity

Authors :
Latkin, Ivan V.
Publication Year :
2023

Abstract

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 Stockmeyer and Meyer method will appreciably be used for this simulation. It will be proved using this modeling that the complexity classes $\mathbf{EXP}$ and $\mathbf{PSPACE}$ coincide; and more generally, the class $(k\!+\!1)$-fold Deterministic Exponential Time equals to the class $k$-fold Deterministic Exponential Space for each $k\geqslant1$; the space complexity of the languages of the class $\mathbf{P}$ will also be studied. Furthermore, this allows us to slightly 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, lower complexity bound of the language recognition<br />Comment: 44 pages, 26 references bibliography; text overlap with arXiv:1907.04521 because the paper is created in the same method

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2311.01184
Document Type :
Working Paper