DTIME - DTIME

В теории сложности вычислений , DTIME (или TIME ) является вычислительным ресурсом по времени вычислений для детерминированной машины Тьюринга . Он представляет собой количество времени (или количество этапов вычислений), которое «нормальный» физический компьютер потребует для решения определенной вычислительной задачи с использованием определенного алгоритма . Это один из наиболее хорошо изученных ресурсов сложности, потому что он так близко соответствует важному реальному ресурсу (времени, которое требуется компьютеру для решения проблемы).

Ресурс DTIME используется для определения классов сложности , наборов всех задач решения, которые могут быть решены с использованием определенного количества времени вычислений. Если проблема размера ввода n может быть решена в , у нас есть класс сложности (или ). Нет ограничений на объем используемой памяти , но могут быть ограничения на некоторые другие ресурсы сложности (например, чередование ). ${\ Displaystyle О (е (п))}$${\ Displaystyle {\ mathsf {DTIME}} (е (п))}$${\ Displaystyle {\ mathsf {ВРЕМЯ}} (е (п))}$

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

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

DTIME удовлетворяет теореме временной иерархии , а это означает, что асимптотически большее количество времени всегда создает строго большие наборы проблем.

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

${\ displaystyle {\ mathsf {P}} = \ bigcup _ {k \ in \ mathbb {N}} {\ mathsf {DTIME}} (n ^ {k})}$

P - наименьший устойчивый класс, который включает задачи с линейным временем (AMS 2004, лекция 2.2, стр. 20). P - один из классов наибольшей сложности, который считается «вычислительно допустимым». ${\ Displaystyle {\ mathsf {DTIME}} \ влево (п \ вправо)}$

Гораздо более крупный класс, использующий детерминированное время, - это EXPTIME , который содержит все проблемы, которые можно решить с помощью детерминированной машины в экспоненциальном времени . Формально у нас есть

${\ displaystyle {\ mathsf {EXPTIME}} = \ bigcup _ {k \ in \ mathbb {N}} {\ mathsf {DTIME}} \ left (2 ^ {n ^ {k}} \ right).}$

Аналогичным образом можно определить классы большей сложности. Благодаря теореме об иерархии времени эти классы образуют строгую иерархию; мы знаем это , и дальше. ${\ Displaystyle {\ mathsf {P}} \ subsetneq {\ mathsf {EXPTIME}}}$

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

Точная модель машины, используемая для определения DTIME, может варьироваться, не влияя на мощность ресурса. Результаты в литературе часто используют многоленты машины Тьюринга , особенно при обсуждении очень малых временных классов. В частности, многолента-детерминированная машина Тьюринга никогда не может обеспечить более чем квадратичное ускорение по времени по сравнению с одинарной.

Мультипликативные константы в используемом количестве времени не изменяют мощность классов DTIME; Постоянное мультипликативное ускорение всегда может быть получено за счет увеличения количества состояний в управлении с конечным числом состояний. В заявлении Пападимитриу для языка L :

Пусть . Тогда для любого , где .${\ displaystyle L \ in {\ mathsf {DTIME}} (f (n))}$${\ displaystyle \ epsilon> 0}$${\ displaystyle L \ in {\ mathsf {DTIME}} (f '(n))}$${\ displaystyle f '(n) = \ epsilon f (n) + n + 2}$

Обобщения

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

${\ Displaystyle {\ mathsf {DTIME}} (О (п)) \ neq {\ mathsf {NTIME}} (О (п))}$

для многоленты. Это было распространено на

${\ displaystyle {\ mathsf {DTIME}} (O (n {\ sqrt {\ log ^ {*} n}})) \ neq {\ mathsf {NTIME}} (O (n {\ sqrt {\ log ^ { *} n}}))}$

пользователя Santhanam.

Если мы используем альтернативную машину Тьюринга , у нас есть ресурс ATIME.

Рекомендации

• Американское математическое общество (2004 г.). Рудич, Стивен и Ави Вигдерсон (ред.). Теория вычислительной сложности . Американское математическое общество и Институт перспективных исследований . ISBN 0-8218-2872-X.
• Пападимитриу, Христос Х. (1994). Вычислительная сложность . Ридинг, Массачусетс: Эддисон-Уэсли. ISBN 0-201-53082-1.