Введение

В теории вычислительной сложности DTIME (или TIME) — это вычислительный ресурс, представляющий время вычислений для детерминированной машины Тьюринга. Он отражает количество времени (или число вычислительных шагов), необходимое обычному физическому компьютеру для решения конкретной вычислительной задачи с использованием определённого алгоритма. Это один из наиболее изученных ресурсов сложности, поскольку он тесно связан с важным реальным ресурсом – временем, затрачиваемым компьютером на решение задачи. Ресурс DTIME используется для определения классов сложности – множеств всех задач принятия решений, которые могут быть решены за определённое время вычислений. Если задачу размера ввода n можно решить за O(f(n)), то мы получаем класс сложности \mathsf{DTIME}(f(n)) (или \mathsf{TIME}(f(n))). Ограничений на объём используемой памяти нет, но могут существовать ограничения на другие ресурсы сложности (например, на чередование).

Классы сложности в DTIME

Многие важные классы сложности определены в терминах DTIME, содержащие все задачи, которые могут быть решены за определенное количество детерминированного времени. Любая допустимая функция сложности может быть использована для определения класса сложности, но только некоторые классы полезны для изучения. В общем случае, мы хотим, чтобы наши классы сложности были устойчивы к изменениям в вычислительной модели и были замкнуты относительно композиции подпрограмм. DTIME удовлетворяет теореме об иерархии времени, что означает, что асимптотически большее время всегда приводит к строго большим множествам задач. Хорошо известный класс сложности P включает в себя все задачи, которые могут быть решены за полиномиальное количество времени DTIME. Формально его можно определить следующим образом:

P – наименьший устойчивый класс, включающий задачи, решаемые за линейное время (AMS 2004, Lecture 2.2, pg. 20). P – один из самых больших классов сложности, считающихся "вычислительно реализуемыми". Гораздо больший класс, использующий детерминированное время, – это EXPTIME, который содержит все задачи, решаемые на детерминированной машине за экспоненциальное время. Формально, мы имеем:

Более крупные классы сложности могут быть определены аналогичным образом. Благодаря теореме об иерархии времени, эти классы образуют строгую иерархию; мы знаем, что , и так далее.

Модель машины

Для надежных классов, таких как P, точная модель машины, используемая для определения DTIME, может варьироваться без изменения вычислительной мощности ресурса. В литературе по вычислительной сложности DTIME часто определяется на основе многоленточных машин Тьюринга, особенно при обсуждении очень малых классов времени. Многоленточная детерминированная машина Тьюринга никогда не может обеспечить ускорение времени более чем в квадратичный раз по сравнению с одноленточной машиной. Благодаря теореме о линейном ускорении для машин Тьюринга, мультипликативные константы в ограничении по времени не влияют на масштаб классов DTIME; постоянное мультипликативное ускорение всегда можно получить, увеличив число состояний в конечном автомате и размер алфавита ленты. Согласно утверждению Пападимитриу, для языка L, Пусть Тогда, для любого , , где .

Обобщения

Используя модель, отличную от детерминированной машины Тьюринга, существуют различные обобщения и ограничения DTIME. Например, если мы используем недетерминированную машину Тьюринга, мы получаем ресурс NTIME. Взаимосвязь между выразительной мощностью DTIME и другими вычислительными ресурсами изучена крайне слабо. Один из немногих известных результатов относится к многоленточным машинам. Сантанамом это было расширено до [формулы]. Если мы используем чередующуюся машину Тьюринга, мы получаем ресурс ATIME.