DTIME - DTIME

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

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

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

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

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

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

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

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

Гораздо больший класс, использующий детерминированное время, - 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} (О (п)) neq mathrm {NTIME} (О (п))}$

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

${ 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.