Abstract:
Classes of time and space complexity of Turing machines are defined, and relationships between them are discussed. New relationships between the defined complexity classes are described.
Key words:$P$ vs $\mathbf{NP}$ problem, $\mathbf{DSPACE}(|X|^n)$ vs $\mathbf{NSPACE}(|X|^n)$, polynomial reducibility (Karp reducibility), $\mathbf{NP}$-complete Turing machines, theory of computational complexity, deterministic Turing machines, nondeterministic Turing machines.
Fulltext:
PDF file (162 kB)