EXPTIME - EXPTIME
В теории сложности вычислений , то класс сложности EXPTIME (иногда называют EXP или DEXPTIME ) является множеством всех задач принятия решений , которые разрешимы с помощью детерминированной машины Тьюринга в экспоненциальное время , т.е. в O (2 р ( п ) ) время, где р ( n ) - полиномиальная функция от n .
EXPTIME - это один интуитивно понятный класс в экспоненциальной иерархии классов сложности со все более сложными оракулами или чередованиями кванторов. Например, класс 2-EXPTIME определяется аналогично EXPTIME, но с двойной экспоненциальной временной границей . Это может быть обобщено на все более высокие временные рамки.
EXPTIME также можно переформулировать как пространственный класс APSPACE, набор всех проблем, которые могут быть решены с помощью переменной машины Тьюринга в полиномиальном пространстве.
EXPTIME относится к другим базовым классам временной и пространственной сложности следующим образом: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE . Более того, по теореме об иерархии времени и теореме о пространственной иерархии известно, что P ⊊ EXPTIME, NP ⊊ NEXPTIME и PSPACE ⊊ EXPSPACE.
Формальное определение
Что касается DTIME ,
Отношения с другими классами
Известно, что
а также по теореме об иерархии времени и теореме о пространственной иерархии , что
В приведенных выше выражениях символ ⊆ означает «является подмножеством», а символ ⊊ означает «является строгим подмножеством».
поэтому по крайней мере одно из первых трех включений и по крайней мере одно из трех последних включений должно быть правильным, но неизвестно, какие именно. Большинство экспертов считают, что все включения правильные. Также известно, что если P = NP , то EXPTIME = NEXPTIME , класс задач, решаемых за экспоненциальное время недетерминированной машиной Тьюринга . Точнее, EXPTIME ≠ NEXPTIME тогда и только тогда , когда существуют редкие языки в НП , которые не являются в P .
EXPTIME можно переформулировать как пространственный класс APSPACE, набор всех проблем, которые могут быть решены альтернативной машиной Тьюринга в полиномиальном пространстве. Это один из способов увидеть, что PSPACE ⊆ EXPTIME, поскольку чередующаяся машина Тьюринга по крайней мере так же мощна, как детерминированная машина Тьюринга.
EXPTIME-завершено
Задача решения является EXPTIME-завершенной, если она находится в EXPTIME, и каждая проблема в EXPTIME имеет полиномиальное сокращение «многие-один» . Другими словами, существует алгоритм с полиномиальным временем , который преобразует экземпляры одного в экземпляры другого с тем же ответом. Проблемы, завершенные EXPTIME, можно рассматривать как самые сложные проблемы в EXPTIME. Обратите внимание, что хотя неизвестно, равно ли NP P, мы знаем, что задачи EXPTIME-complete не находятся в P; с помощью теоремы об иерархии времени было доказано, что эти проблемы не могут быть решены за полиномиальное время .
В теории вычислимости одной из основных неразрешимых проблем является проблема остановки : определение того, останавливается ли детерминированная машина Тьюринга (DTM). Одна из самых фундаментальных проблем EXPTIME-complete - это более простая версия, которая спрашивает, останавливается ли DTM не более чем за k шагов. Это в EXPTIME, потому что тривиальная симуляция требует O ( k ) времени, а вход k кодируется с использованием O (log k ) битов, что вызывает экспоненциальное количество симуляций. Он является полным EXPTIME, потому что, грубо говоря, мы можем использовать его, чтобы определить, принимает ли машина, решающая задачу EXPTIME, экспоненциальное количество шагов; он больше не будет использовать. Та же проблема с количеством шагов, записанных в унарном языке, является P-полной .
Другие примеры EXPTIME-полных задач включают задачу оценки позиции в общих шахматах , шашках или го (с японскими правилами ко). Эти игры могут быть завершены EXPTIME, потому что игры могут длиться несколько ходов, которые экспоненциально зависят от размера доски. В примере Го японское правило ко достаточно трудноразрешимо, чтобы подразумевать полноту EXPTIME, но неизвестно, являются ли более гибкие американские или китайские правила игры полными EXPTIME.
Напротив, обобщенные игры, которые могут длиться несколько ходов, полиномиальных по размеру доски, часто являются PSPACE-полными . То же самое и с экспоненциально длинными играми, в которых неповторение происходит автоматически.
Другой набор важных проблем EXPTIME-complete относится к лаконичным схемам . Краткие схемы - это простые машины, используемые для описания некоторых графов в экспоненциально меньшем пространстве. Они принимают два номера вершины в качестве входных и выходных данных о том, есть ли между ними ребро. Для многих естественных Р-полных задач графа, где граф выражается в естественном представлении , такие как матрицы смежности , решая ту же проблему на представление сжатой схемы является EXPTIME-полным, так как входной сигнал экспоненциально меньше; но это требует нетривиального доказательства, поскольку сжатые схемы могут описывать только подкласс графов.