Введение
При большем количестве времени машина Тьюринга может решать больше задач. В теории вычислительной сложности теоремы об иерархии времени являются важными утверждениями об вычислениях с ограничением по времени на машинах Тьюринга. Неформально, эти теоремы утверждают, что при наличии большего времени машина Тьюринга может решать больше задач. Например, существуют задачи, которые могут быть решены за время n², но не за время n, где n — длина входных данных. Теорема об иерархии времени для детерминированных многоленточных машин Тьюринга была впервые доказана Ричардом Э. Стернсом и Юрисом Хартманисом в 1965 году. Она была улучшена годом позже, когда Ф. С. Хенни и Ричард Э. Стернс повысили эффективность универсальной машины Тьюринга. Как следствие этой теоремы, для каждого детерминированного класса сложности с ограничением по времени существует строго больший класс сложности с ограничением по времени, и, следовательно, иерархия классов сложности с ограничением по времени не схлопывается полностью. Более точно, теорема об иерархии времени для детерминированных машин Тьюринга гласит, что для всех конструктивных по времени функций f(n), , где DTIME(f(n)) обозначает класс сложности задач принятия решений, разрешимых за время O(f(n)). Левый класс включает в себя обозначение «малое о», относящееся к множеству задач принятия решений, разрешимых асимптотически за время меньше, чем f(n). В частности, это показывает, что если и только если , таким образом, мы имеем бесконечную иерархию времени. Теорема об иерархии времени для недетерминированных машин Тьюринга была первоначально доказана Стивеном Куком в 1972 году. Она была улучшена до своей нынешней формы посредством сложного доказательства Джоэлем Сейферасом, Майклом Фишером и Альбертом Мейером в 1978 году. Наконец, в 1983 году Станислав Жак получил тот же результат с помощью простого доказательства, которое преподается и сегодня. Теорема об иерархии времени для недетерминированных машин Тьюринга утверждает, что если g(n) — конструктивная по времени функция, и f(n+1) = o(g(n)), то .
In computational complexity theory, the time hierarchy theorems are important statements about time bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n2 time but not n time, where n is the input length. The time hierarchy theorem for deterministic multi tape Turing machines was first proven by Richard E. Stearns and Juris Hartmanis in 1965. It was improved a year later when F. C. Hennie and Richard E. Stearns improved the efficiency of the Universal Turing machine. Consequent to the theorem, for every deterministic time bounded complexity class, there is a strictly larger time bounded complexity class, and so the time bounded hierarchy of complexity classes does not completely collapse. More precisely, the time hierarchy theorem for deterministic Turing machines states that for all time constructible functions f(n),
,
where DTIME(f(n)) denotes the complexity class of decision problems solvable in time O(f(n)). The left hand class involves little o notation, referring to the set of decision problems solvable in asymptotically less than f(n) time. In particular, this shows that if and only if , so we have an infinite time hierarchy. The time hierarchy theorem for nondeterministic Turing machines was originally proven by Stephen Cook in 1972. It was improved to its current form via a complex proof by Joel Seiferas, Michael Fischer, and Albert Meyer in 1978. Finally in 1983, Stanislav Žák achieved the same result with the simple proof taught today. The time hierarchy theorem for nondeterministic Turing machines states that if g(n) is a time constructible function, and f(n+1) = o(g(n)), then
Аналогичные теоремы для пространства называются теоремами об иерархии пространства. Подобной теоремы для классов вероятностной сложности с ограничением по времени не известно, если только класс также не имеет одного бита подсказки.
Предыстория
Обе теоремы используют понятие функции, конструируемой по времени. Функция является конструируемой по времени, если существует детерминированная машина Тьюринга, такая что для каждого n, если машина запущена с входом, состоящим из n единиц, она остановится ровно через f(n) шагов. Все многочлены с неотрицательными целыми коэффициентами конструируемы по времени, как и экспоненциальные функции, такие как 2^n.
Обзор доказательств
Нам нужно доказать, что некоторый класс времени TIME(g(n)) строго больше, чем некоторый класс времени TIME(f(n)). Мы делаем это, конструируя машину, которая не принадлежит классу TIME(f(n)), методом диагонализации. Затем мы показываем, что эта машина принадлежит классу TIME(g(n)), используя машину-симулятор.
Заявление
Теорема об иерархии времени. Если f(n) – конструктивная по времени функция, то существует задача принятия решения, которая не может быть решена за детерминированное время в худшем случае o(f(n)), но может быть решена за детерминированное время в худшем случае O(f(n)log f(n)). Таким образом,
Примечание 1. f(n) не меньше, чем n, поскольку функции меньшего размера никогда не являются конструктивными по времени. Пример. Существуют задачи, разрешимые за время nlog₂n, но не разрешимые за время n. Это следует из того, что n входит в…