Введение

В теории вычислительной сложности класс сложности NEXPTIME (иногда называемый NEXP) представляет собой множество задач принятия решений, которые могут быть решены недетерминированной машиной Тьюринга за время. В терминах NTIME,

Альтернативно, NEXPTIME можно определить, используя детерминированные машины Тьюринга в качестве проверяющих. Язык L принадлежит NEXPTIME тогда и только тогда, когда существуют полиномы p и q, и детерминированная машина Тьюринга M, такие что:
Для всех x и y машина M работает за время на входе (x,y).
Для всех x, принадлежащих L, существует строка y длиной такая, что M(x,y) = 1.
Для всех x, не принадлежащих L, и всех строк y длиной , M(x,y) = 0.
Мы знаем,

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

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

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

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

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

NEXPTIME-полный

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