Введение
Ускорение машин Тьюринга за счет повышения сложности символов ленты
В теории вычислительной сложности линейная теорема об ускорении для машин Тьюринга утверждает, что для любого действительного числа c > 0 и любой k-ленточной машины Тьюринга, решающей задачу за время f(n), существует другая k-ленточная машина, решающая ту же задачу за время не более f(n)/c + 2n + 3, где k > 1. Если исходная машина недетерминированная, то новая машина также недетерминированная. Константы 2 и 3 в выражении 2n + 3 могут быть уменьшены, например, до n + 2.
In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any k tape Turing machine solving a problem in time f(n), there is another k tape machine that solves the same problem in time at most f(n)/c + 2n + 3, where k > 1. If the original machine is non deterministic, then the new machine is also non deterministic. The constants 2 and 3 in 2n + 3 can be lowered, for example, to n + 2.
Машины с одной лентой
Для одноленточных машин Тьюринга линейный выигрыш в скорости выполняется для машин с временем выполнения не менее T. Строго доказано, что это не выполняется для машин с временем. Показано, что для недетерминированных одноленточных машин Тьюринга со сложностью по времени T линейный выигрыш в скорости может быть достигнут без увеличения алфавита.
nondeterministic single tape Turing machines of time complexity linear speedup can be achieved without increasing the alphabet.
Зависимость от формы хранения
Риган рассматривал свойство вычислительной модели, называемое информационной окрестностью. Это свойство связано со структурой памяти: машина Тьюринга обладает линейной окрестностью, тогда как машина Колмогорова-Успенского и другие указательные машины – экспоненциальной. Гипотеза Регана заключается в том, что существование линейного ускорения связано с наличием полиномиальной информационной окрестности. Ключевой момент этого утверждения состоит в том, что модель с экспоненциальной окрестностью не сможет достичь ускорения, даже если разрешено изменение алфавита (для моделей с дискретной памятью, хранящей символы). Однако Реган не доказал никакой общей теоремы подобного рода. Хюне доказал, что если требуется, чтобы ускорение было получено посредством онлайн-симуляции (что имеет место для ускорения на обычных машинах Тьюринга), то линейное ускорение невозможно на машинах с древовидной памятью.