Теоремы о временно́й иерархии для машин с произвольным доступом к памяти

В работе рассматривается вопрос о времени распознавания множеств слов: на машине с произвольным доступом к памяти. Основной результат, полученный в статье, утверждает, что для всякой функции $T(n)$, которая может быть вычислена на машине с произвольным доступом к памяти за время $\widehat T(n)$, существует множество слов $A$ в двубуквенном алфавите, распознаваемое некоторой машиной за время $21T(n)+6\widetilde T(n)+25n$, но которое не распознается за время $T(n)$. Доказательство этого результата состоит в построении такого множества с использованием диагональной процедуры. Он является усилением теоремы Кука–Рекхоу о временной иерархии. Затем определяется класс функций $\mathscr T$, содержащий многие функции (например, полиномы степени выше единицы, $n\log n$, $2^{\sqrt n}$ и др.), представляющие интерес как оценки сложности. Для класса $\mathscr T$ доказывается теорема, уточняющая основной результат для функций из этого класса. Он состоит в том, что для любой функции $T(n)\in\mathscr T$ и любого $c>1$ существует множество слов, распознаваемое за время $cT(n)$ некоторой машиной с произвольным доступом к памяти, но не распознаваемое за время $T(n)$. Рассматриваются также машины с произвольным доступом к памяти с ограничением на длину ячейки; приводятся результаты, связывающие время работы такой машины со временем работы машины без ограничений на длину ячейки. Библ. – 4 назв.