ЭКСПТАЙМ

В теории сложности вычислений класс сложности EXPTIME (иногда называемый EXP или DEXPTIME ) представляет собой множество всех задач принятия решений , которые могут быть решены детерминированной машиной Тьюринга за экспоненциальное время , т. е. за время O (2p ^{( n ) ) , где} p ( n ) — полиномиальная функция от n .

EXPTIME — это один интуитивно понятный класс в экспоненциальной иерархии классов сложности со все более сложными оракулами или чередованиями квантификаторов. Например, класс 2-EXPTIME определяется аналогично EXPTIME, но с двойной экспоненциальной временной границей. Это можно обобщить на все более высокие временные границы.

EXPTIME можно также переформулировать как пространственный класс APSPACE, множество всех задач, которые могут быть решены с помощью альтернативной машины Тьюринга в полиномиальном пространстве.

EXPTIME соотносится с другими базовыми классами сложности времени и пространства следующим образом: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE . Кроме того, по теореме об иерархии времени и теореме об иерархии пространства известно, что P ⊊ EXPTIME, NP ⊊ NEXPTIME и PSPACE ⊊ EXPSPACE.

С точки зрения DTIME ,

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

Известно, что

а также, по теореме об иерархии времени и теореме об иерархии пространства , что

В приведенных выше выражениях символ ⊆ означает «является подмножеством», а символ ⊊ означает «является строгим подмножеством».

поэтому по крайней мере одно из первых трех включений и по крайней мере одно из последних трех включений должны быть правильными, но неизвестно, какие из них являются правильными. Также известно, что если P = NP , то EXPTIME = NEXPTIME , класс задач, решаемых за экспоненциальное время недетерминированной машиной Тьюринга . ^[1] Точнее, E ≠ NE тогда и только тогда, когда существуют разреженные языки в NP , которых нет в P . ^[2]

EXPTIME можно переформулировать как класс пространства APSPACE, множество всех задач, которые могут быть решены с помощью альтернативной машины Тьюринга в полиномиальном пространстве. Это один из способов увидеть, что PSPACE ⊆ EXPTIME, поскольку альтернативная машина Тьюринга по крайней мере столь же мощна, как и детерминированная машина Тьюринга. ^[3]

Задача принятия решения является EXPTIME-полной, если она находится в EXPTIME, и каждая задача в EXPTIME имеет полиномиальное время сведения ко многим единицам . Другими словами, существует полиномиальный алгоритм , который преобразует экземпляры одной в экземпляры другой с тем же ответом. Задачи, которые являются EXPTIME-полными, можно считать самыми сложными задачами в EXPTIME. Обратите внимание, что хотя неизвестно, равно ли NP P, мы знаем, что EXPTIME-полные задачи не находятся в P; было доказано, что эти задачи не могут быть решены за полиномиальное время по теореме об иерархии времени .

В теории вычислимости одной из основных неразрешимых проблем является проблема остановки : определение того, останавливается ли детерминированная машина Тьюринга (DTM). Одна из самых фундаментальных EXPTIME-полных проблем — это более простая версия этой, которая спрашивает, останавливается ли DTM на заданном входе не более чем за k шагов. Она находится в EXPTIME, потому что тривиальное моделирование требует O( k ) времени, а вход k кодируется с использованием O(log k ) бит, что приводит к экспоненциальному числу симуляций. Она EXPTIME-полная, потому что, грубо говоря, мы можем использовать ее для определения, принимает ли машина, решающая задачу EXPTIME, экспоненциальное число шагов; она не будет использовать больше. ^[4] Та же проблема с числом шагов, записанная в унарной форме, является P-полной .

Другие примеры EXPTIME-полных задач включают задачу оценки позиции в обобщенных шахматах , ^[5] шашках , ^[6] или го (с японскими правилами ко). ^[7] Эти игры имеют шанс быть EXPTIME-полными, поскольку игры могут длиться в течение количества ходов, экспоненциально зависящего от размера доски. В примере с го японское правило ко, как известно, подразумевает EXPTIME-полность, но неизвестно, являются ли американские или китайские правила для игры EXPTIME-полными (они могут варьироваться от PSPACE до EXPSPACE).

Напротив, обобщенные игры, которые могут длиться в течение числа ходов, полиномиального по размеру доски, часто являются PSPACE-полными . То же самое относится к экспоненциально длинным играм, в которых неповторение происходит автоматически.

Другой набор важных EXPTIME-полных задач относится к кратким схемам. краткие схемы — это простые машины, используемые для описания некоторых графов в экспоненциально меньшем пространстве. Они принимают два числа вершин в качестве входных данных и выводят, есть ли ребро между ними. Для многих естественных P-полных задач графа, где граф выражен в естественном представлении, таком как матрица смежности , решение той же задачи на кратком представлении схемы является EXPTIME-полным, потому что входные данные экспоненциально меньше; но это требует нетривиального доказательства, поскольку краткие схемы могут описывать только подкласс графов. ^[8]