Аннотация:
В работе определяются классы временной и пространственной сложности машин Тьюринга и рассматриваются соотношения между ними. Представлены также новые соотношения между введенными классами сложности. Библ. 13.
Ключевые слова:проблема “$P$ vs $\mathbf{NP}$”, “$\mathbf{DSPACE}(|X|^n)$ vs $\mathbf{NSPACE}(|X|^n)$”, полиномиальная сводимость (сводимость по Карпу), $\mathrm{NP}$-полные машины Тьюринга, теория сложности вычислений, детерминированные машины Тьюринга, недетерминированные машины Тьюринга.
УДК:519.7
Поступила в редакцию: 07.07.2016 Исправленный вариант: 06.09.2016
Полный текст:
PDF файл (162 kB)