ВРЕМЯ ЭКСПРЕСС

«EXP» перенаправляется сюда. Чтобы узнать о других значениях, см. Exp .

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

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

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

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

Формальное определение

Что касается DTIME ,

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

Отношения с другими классами

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

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE

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

P ⊊ EXPTIME, NP ⊊ NEXPTIME и PSPACE ⊊ EXPSPACE.

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

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

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

EXPTIME-завершено

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

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

Другие примеры EXPTIME-полных задач включают задачу оценки позиции в обобщенных шахматах . шашки , или Го (по японским правилам ко). У этих игр есть шанс завершить EXPTIME, поскольку игра может длиться определенное количество ходов, экспоненциально зависящее от размера доски. В примере с Го известно, что японское правило ко подразумевает EXPTIME-полноту, но неизвестно, являются ли американские или китайские правила игры EXPTIME-полными (они могут варьироваться от PSPACE до EXPSPACE).

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

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