СЛЕДУЮЩЕЕ - NEXPTIME

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

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

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

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

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

Мы знаем

P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME

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

NP ⊊ NEXPTIME

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

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

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- полным.

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

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

Ссылки

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