Введение
В теории вычислительной сложности класс сложности EXPTIME (иногда называемый EXP или DEXPTIME) представляет собой множество всех задач принятия решений, разрешимых детерминированной машиной Тьюринга за экспоненциальное время, то есть за время O(2p(n)), где p(n) — полиномиальная функция от n.
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i. e., in O(2p(n)) time, where p(n) is a polynomial function of n.
EXPTIME is one intuitive class in an exponential hierarchy of complexity classes with increasingly more complex oracles or quantifier alternations. For example, the class 2 EXPTIME is defined similarly to EXPTIME but with a doubly exponential time bound. This can be generalized to higher and higher time bounds. EXPTIME can also be reformulated as the space class APSPACE, the set of all problems that can be solved by an alternating Turing machine in polynomial space. EXPTIME relates to the other basic time and space complexity classes in the following way: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE. Furthermore, by the time hierarchy theorem and the space hierarchy theorem, it is known that P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE.
EXPTIME является одним из интуитивно понятных классов в экспоненциальной иерархии классов сложности с возрастающей сложностью оракулов или чередования кванторов. Например, класс 2-EXPTIME определяется аналогично EXPTIME, но с ограничением по времени, равным двойной экспоненте. Это можно обобщить на более высокие ограничения по времени. EXPTIME также можно переформулировать как пространственный класс APSPACE, то есть множество всех задач, разрешимых чередующейся машиной Тьюринга в полиномиальном пространстве. EXPTIME соотносится с другими основными классами временной и пространственной сложности следующим образом: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE. Более того, согласно теореме об иерархии времени и теореме об иерархии пространства, известно, что P ⊂ EXPTIME, NP ⊂ NEXPTIME и PSPACE ⊂ EXPSPACE.
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i. e., in O(2p(n)) time, where p(n) is a polynomial function of n.
EXPTIME is one intuitive class in an exponential hierarchy of complexity classes with increasingly more complex oracles or quantifier alternations. For example, the class 2 EXPTIME is defined similarly to EXPTIME but with a doubly exponential time bound. This can be generalized to higher and higher time bounds. EXPTIME can also be reformulated as the space class APSPACE, the set of all problems that can be solved by an alternating Turing machine in polynomial space. EXPTIME relates to the other basic time and space complexity classes in the following way: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE. Furthermore, by the time hierarchy theorem and the space hierarchy theorem, it is known that P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE.
EXPTIME-полный
Проблема принятия решения является EXPTIME-полной, если она принадлежит классу EXPTIME и любая задача из EXPTIME полиномиально сводится к ней. Иными словами, существует алгоритм, работающий за полиномиальное время, который преобразует экземпляры одной задачи в экземпляры другой с тем же ответом. Задачи, являющиеся EXPTIME-полными, можно считать самыми сложными задачами в классе EXPTIME. Следует отметить, что хотя неизвестно, равны ли NP и P, мы знаем, что EXPTIME-полные задачи не принадлежат классу P; доказано, что эти задачи нельзя решить за полиномиальное время, согласно теореме об иерархии времени. В теории вычислимости одной из основных неразрешимых задач является проблема останова: определение, останавливается ли детерминированная машина Тьюринга (ДМТ). Одной из фундаментальных EXPTIME-полных задач является упрощенная версия этой проблемы, которая спрашивает, остановится ли ДМТ на заданном входе не более чем за k шагов. Она принадлежит классу EXPTIME, поскольку тривиальная симуляция требует O(k) времени, а вход k кодируется с использованием O(log k) бит, что приводит к экспоненциальному числу симуляций. Она является EXPTIME-полной, поскольку, грубо говоря, её можно использовать для определения, принимает ли машина, решающая EXPTIME-задачу, за экспоненциальное число шагов; больше шагов ей не потребуется. Та же задача, но с числом шагов, записанным унарно, является P-полной. Другие примеры EXPTIME-полных задач включают проблему оценки позиции в обобщенных шахматах, шашках или го (с японскими правилами ко). Эти игры могут быть EXPTIME-полными, поскольку количество ходов в игре может быть экспоненциальным по отношению к размеру доски. В примере с игрой го, японское правило ко известно как необходимое условие EXPTIME-полноты, но неизвестно, являются ли американские или китайские правила для этой игры EXPTIME-полными (они могут варьироваться от PSPACE до EXPSPACE). Напротив, обобщенные игры, в которых количество ходов полиномиально по отношению к размеру доски, часто являются PSPACE-полными. То же самое верно и для экспоненциально длинных игр, в которых повторение ходов исключено автоматически. Другой важный класс EXPTIME-полных задач связан с лаконичными схемами. Лаконичные схемы – это простые машины, используемые для описания некоторых графов в экспоненциально меньшем объеме памяти. Они принимают на вход номера двух вершин и выдают результат, указывающий, есть ли между ними ребро. Для многих естественных P-полных задач о графах, где граф представлен в естественной форме, например, матрицей смежности, решение той же задачи для представления в виде лаконичной схемы является EXPTIME-полным, поскольку вход экспоненциально меньше; однако это требует нетривиального доказательства, поскольку лаконичные схемы могут описывать только подкласс графов.