EXPTIME

редактировать

Алгоритмический класс сложности

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

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

Содержание

1 Формальное определение
2 Отношения с другими классами
3 EXPTIME-complete
4 Ссылки

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

В терминах DTIME,

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

{\ displaystyle {\ 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, класс задач, решаемых за экспоненциальное время недетерминированной машиной Тьюринга. Точнее, EXPTIME ≠ NEXPTIME, если и только если существуют разреженные языки в NP, которых нет в P.

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

EXPTIME-complete

Проблема принятия решения является 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-complete.

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

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

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

Ссылки