В теории сложности вычислений , то класс сложности NEXPTIME (иногда называемый Nexp ) есть множество проблем решения , которые могут быть решены с помощью недетерминистических машин Тьюринга с использованием времени .
Что касается NTIME ,
В качестве альтернативы, NEXPTIME может быть определен с использованием детерминированных машин Тьюринга в качестве верификаторов. Язык L в NEXPTIME тогда и только тогда , когда существуют многочлены р и д , и детерминированный машины Тьюринга M , такие , что
- Для всех x и y машина M работает во времени при вводе
- Для всех x в L существует строка y такой длины , что
- Для всех x, не принадлежащих L, и всех строк длины y ,
Мы знаем
а также по теореме об иерархии времени , что
- NP ⊊ NEXPTIME
Если P = NP , то NEXPTIME = EXPTIME ( аргумент заполнения ); точнее, E ≠ NE тогда и только тогда , когда существуют редкие языки в НП , которые не являются в P . [1]
Альтернативные характеристики [ править ]
NEXPTIME часто возникает в контексте интерактивных систем доказательства , где его можно охарактеризовать двумя способами. Первая - это система доказательства MIP , где у нас есть два всемогущих доказывающих, которые взаимодействуют с рандомизированным верификатором с полиномиальным временем (но не друг с другом). Если строка написана на языке, они должны с большой вероятностью убедить проверяющего в этом. Если строка не на языке, они не должны иметь возможность совместно обмануть проверяющего и заставить его принять строку, кроме как с малой вероятностью. Тот факт, что системы доказательства MIP могут решить любую проблему в NEXPTIME , весьма впечатляет, если учесть, что, когда присутствует только один доказывающий, мы можем распознать только всеPSPACE ; способность проверяющего «перекрестно исследовать» двух проверяющих придает ему огромную силу. См. Интерактивную систему проверки № MIP для получения более подробной информации.
Другая интерактивная система доказательств, характеризующая NEXPTIME, - это определенный класс вероятностно проверяемых доказательств . Напомним, что NP можно рассматривать как класс проблем, в которых всемогущий доказывающий дает предполагаемое доказательство того, что строка находится в языке, а детерминированная машина полиномиального времени проверяет, что это действительное доказательство. Мы вносим два изменения в эту настройку:
- Добавьте случайность, возможность подбрасывать монеты в верификатор.
- Вместо того, чтобы просто давать предполагаемое доказательство проверяющему на ленте, предоставьте ему произвольный доступ к доказательству. Проверяющий может указать индекс в строке доказательства и получить соответствующий бит. Поскольку верификатор может записать индекс полиномиальной длины, он потенциально может индексировать в экспоненциально длинную строку доказательства.
Эти два расширения вместе значительно расширяют возможности системы доказательства, позволяя ей распознавать все языки в NEXPTIME . Класс называется PCP (поли, поли). Более того, в этой характеристике верификатор может быть ограничен чтением только постоянного числа битов, то есть NEXPTIME = PCP (poly, 1). См. Вероятностно проверяемые доказательства для более подробной информации.
NEXPTIME-complete [ править ]
Проблема принятия решения является NEXPTIME-завершенной, если она находится в NEXPTIME, и каждая проблема в NEXPTIME имеет полиномиальное сокращение до многих единиц . Другими словами, существует алгоритм с полиномиальным временем , который преобразует экземпляры одного в экземпляры другого с тем же ответом. Проблемы, которые завершаются NEXPTIME, можно рассматривать как самые сложные проблемы в NEXPTIME. Мы знаем, что NEXPTIME-полные проблемы не находятся в NP; было доказано, что эти проблемы не могут быть проверены за полиномиальное время с помощью теоремы об иерархии времени .
Важный набор неполных проблем NEXPTIME относится к лаконичным схемам . Краткие схемы - это простые машины, используемые для описания графов в экспоненциально меньшем пространстве. Они принимают два номера вершины в качестве входных и выходных данных, есть ли между ними ребро. Если решение задачи на графе в естественном представлении, таком как матрица смежности , является NP-полным , то решение той же проблемы на кратком представлении схемы является NEXPTIME- полным, потому что входные данные экспоненциально меньше (при некотором мягком условии, что снижение NP-полноты достигается за счет «проекции»). [2] [3] В качестве одного простого примера, поиск гамильтонова путидля закодированного таким образом графа является NEXPTIME -полным.
См. Также [ править ]
Ссылки [ править ]
- ^ Юрис Хартманис, Нил Иммерман, Вивиан Сьюельсон. Редкие наборы в NP-P: EXPTIME против NEXPTIME. Информация и управление , том 65, выпуск 2/3, стр.158–181. 1985. В цифровой библиотеке ACM
- ^ К. Пападимитриу и М. Яннакакис , Заметка о сжатых представлениях графиков , Информация и управление, том 71, номер 3, декабрь 1986, стр. 181-185, DOI : 10.1016 / S0019-9958 (86) 80009-2
- ^ C. Пападимитриу. Вычислительная сложность Аддисон-Уэсли, 1994. ISBN 0-201-53082-1 . Раздел 20.1, стр. 492.
- Зоопарк сложности : NEXP , Зоопарк сложности : coNEXP
- Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход , Кембридж , стр. 57, ISBN 978-0-521-42426-4