DTIME

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

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

Классы сложности в DTIME [ править ]

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

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

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

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

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

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

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

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

Модель машины [ править ]

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

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

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

Обобщения [ править ]

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

${\displaystyle \mathrm {DTIME} (O(n))\neq \mathrm {NTIME} (O(n))}$

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

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

пользователя Santhanam. ^[4]

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

Ссылки [ править ]

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