СЛЕДУЮЩЕЕ ВРЕМЯ

В теории сложности вычислений класс сложности NEXPTIME (иногда называемый NEXP ) представляет собой набор задач решения , которые могут быть решены недетерминированной машиной Тьюринга с использованием времени. $2^{n^{O(1)}}$.

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

${\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})$

Альтернативно, NEXPTIME можно определить с использованием детерминированных машин Тьюринга в качестве верификаторов. Язык тогда и только тогда , L находится в NEXPTIME когда существуют полиномы p и q и детерминированная машина Тьюринга M такие, что

• Для всех x и y машина M работает за время. $2^{p(|x|)}$ на входе ⁠ $(x,y)$⁠
• Для всех x в L существует строка y длины $2^{q(|x|)}$ такой, что ⁠ $M(x,y)=1$⁠
• Для всех x не из L и всех строк y длины $2^{q(|x|)}$, ⁠ $M(x,y)=0$⁠

Мы знаем

P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME

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

НП ⊊ НЭКСПАЙМ

Если P = NP , то NEXPTIME = EXPTIME ( аргумент заполнения ); точнее, E ≠ NE существуют разреженные языки тогда и только тогда, когда в NP , которых нет в P .

Альтернативные характеристики

В описательной сложности наборы натуральных чисел, которые можно распознать в NEXPTIME, — это именно те наборы, которые образуют спектр предложения , набор размеров конечных моделей некоторого логического предложения.

NEXPTIME часто возникает в контексте интерактивных систем доказательства , где у него есть две основные характеристики. Первая — это система доказательств MIP , в которой у нас есть два всемогущих доказывающих устройства, которые взаимодействуют со рандомизированным проверяющим устройством, работающим за полиномиальное время (но не друг с другом). Если строка находится на языке, они должны с высокой вероятностью убедить в этом проверяющего. Если строка не соответствует языку, они не должны иметь возможность совместно обманом заставить проверяющего принять строку, за исключением случаев с низкой вероятностью. Тот факт, что системы доказательства MIP могут решить любую проблему в NEXPTIME, весьма впечатляет, если учесть, что когда присутствует только один проверяющий, мы можем распознать только весь PSPACE ; Способность проверяющего «перекрестно допрашивать» двух доказывающих дает ему огромную силу. см. в интерактивной системе доказательств #MIP Дополнительную информацию .

Другая система интерактивных доказательств, характеризующая NEXPTIME, — это определенный класс вероятностно проверяемых доказательств . Напомним, что NP можно рассматривать как класс задач, в которых всемогущее доказывающее устройство дает предполагаемое доказательство того, что строка присутствует в языке, а детерминированная машина с полиномиальным временем проверяет, что это действительное доказательство. Мы вносим два изменения в эту настройку:

• Добавьте в машину-верификатор случайность, возможность подбрасывать монеты.
• Вместо того, чтобы просто предоставить проверяющему предполагаемое доказательство на ленте, предоставьте ему произвольный доступ к доказательству. Верификатор может указать индекс в строке доказательства и получить соответствующий бит. Поскольку верификатор может записать индекс полиномиальной длины, он потенциально может индексировать экспоненциально длинную строку доказательства.

Вместе эти два расширения значительно расширяют возможности системы проверки, позволяя ей распознавать все языки в NEXPTIME . Класс называется PCP (поли, поли). Более того, в этой характеристике верификатор может быть ограничен чтением только постоянного количества битов, т.е. NEXPTIME = PCP (poly, 1). см. в разделе вероятностно проверяемые доказательства Более подробную информацию .

NEXPTIME-завершено

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

Важный набор NEXPTIME -полных задач относится к кратким схемам . Краткие схемы — это простые машины, используемые для описания графов в экспоненциально меньшем пространстве. Они принимают два номера вершин в качестве входных и выходных данных, независимо от того, есть ли между ними ребро. Если решение задачи на графе в естественном представлении, таком как матрица смежности , является NP-полным , то решение той же задачи на кратком представлении схемы является NEXPTIME -полным, поскольку входные данные экспоненциально меньше (при некоторых мягких условиях, которые снижение NP-полноты достигается «проекцией»). В качестве одного простого примера, поиск гамильтонова пути для закодированного таким образом графа является NEXPTIME -завершенным.

См. также

• Сложность игры
• НАПРИМЕР
• ВРЕМЯ ЭКСПРЕСС

Ссылки

• Зоопарк сложности : NEXP , Зоопарк сложности : coNEXP
• Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход , Кембридж , стр. 57, ISBN  978-0-521-42426-4