NEXPTIME - NEXPTIME

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

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

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

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

• Для всех Икс и у, машина M бежит во времени ${ Displaystyle 2 ^ {п (| х |)}}$ на входе ${ Displaystyle (х, у)}$
• Для всех Икс в L, существует строка у длины ${ Displaystyle 2 ^ {д (| х |)}}$ такой, что ${ Displaystyle М (х, у) = 1}$
• Для всех Икс не в L и все струны у длины ${ Displaystyle 2 ^ {д (| х |)}}$, ${ Displaystyle М (х, у) = 0}$

Мы знаем

п ⊆ НП ⊆ EXPTIME ⊆ NEXPTIME

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

NP ⊊ NEXPTIME

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

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

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

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

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

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

NEXPTIME-завершено

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

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

Смотрите также

• Сложность игры
• НП
• EXPTIME

использованная литература

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