DTIME

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

Ресурс DTIME используется для определения классов сложности, наборов всех задач принятия решений, которые могут быть решены с использованием определенного количества время вычисления. Если проблема размера ввода n может быть решена за $O\; (f\; (n))\; \{\backslash \; displaystyle\; O\; (f\; (n))\}$, у нас есть класс сложности $DTIME\; (f\; (п))\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{DTIME\}\; (f\; (n))\}$(или $TIME\; (f\; (n))\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{TIME\}\; (f\; (n))\}$). Нет ограничений на объем используемого пространства памяти , но могут быть ограничения на некоторые другие ресурсы сложности (например, чередование ).

• 1 Классы сложности в DTIME
• 2 Модель машины
• 3 Обобщения
• 4 Ссылки

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

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

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

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

P- наименьший надежный класс, который включает задачи линейного времени $DTIME\; (n)\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{DTIME\}\; \backslash \; left\; (n\; \backslash \; right)\}$(AMS 2004, Лекция 2.2, стр.20). P - один из классов наибольшей сложности, считающихся «вычислительно возможными».

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

$E\; X\; P\; T\; I\; M\; E\; =\; \bigcup \; k\; \in \; N\; D\; T\; I\; M\; E\; (2\; n\; k).\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{EXPTIME\}\; =\; \backslash \; bigcup\; \_\; \{k\; \backslash \; in\; \backslash \; mathbb\; \{N\}\}\; \backslash \; mathrm\; \{DTIME\}\; \backslash \; left\; (2\; ^\; \{n\; ^\; \{k\}\}\; \backslash \; right).\}$

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

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

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

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

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

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

для многоленточных машин. Это было расширено до

$DTIME\; (O\; (n\; log\; \ast \; \; n))\; \ne \; NTIME\; (О\; (п\; ло\; g\; *\; \; n))\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{DTIME\}\; (O\; (n\; \{\backslash \; sqrt\; \{\backslash \; log\; ^\; \{*\}\; n\}\}))\; \backslash \; neq\; \backslash \; mathrm\; \{NTIME\}\; (O\; (n\; \{\backslash \; sqrt\; \{\backslash \; log\; ^\; \{*\}\; n\}\}))\}$

от Santhanam.

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

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