WikiDer > NEXPTIME

NEXPTIME

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

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

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

  • Для всех Икс и у, машина M бежит во времени на входе
  • Для всех Икс в L, существует строка у длины такой, что
  • Для всех Икс не в L и все струны у длины ,

Мы знаем

пНП ⊆ EXPTIME ⊆ NEXPTIME

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

NP ⊊ NEXPTIME

Если P = NP, тогда NEXPTIME = EXPTIME (аргумент заполнения); точнее, ENE тогда и только тогда, когда существуют редкие языки в НП что не в п.[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-полный.

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

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

  1. ^ Юрис Хартманис, Нил Иммерман, Вивиан Севельсон. Редкие наборы в NP-P: EXPTIME против NEXPTIME. Информация и контроль, том 65, выпуск 2/3, стр 158–181. 1985 г. В цифровой библиотеке ACM
  2. ^ К. Пападимитриу & М. Яннакакис, Замечание о лаконичном представлении графов, Информация и контроль, том 71, номер 3, декабрь 1986 г., стр. 181–185, Дои:10.1016 / S0019-9958 (86) 80009-2
  3. ^ C. Papadimitriou. Вычислительная сложность Аддисон-Уэсли, 1994. ISBN 0-201-53082-1. Раздел 20.1, стр. 492.