NEXP-полные проблемы

31

Вокруг множество проблем с NP-полнотой, и источники их собирают, например, см. Книгу Гэри и Джонсона. Мне было бы интересно увидеть список неполных NEXP задач. Есть ли один доступный? Поскольку я предполагаю, что нет, я открываю этот вопрос (это должна быть вики сообщества? Я не знаю об этом материале).

В идеале список должен охватывать различные «типы» неполных NEXP задач, возможно, с некоторой избыточностью, чтобы получить общую картину, но без повторения слишком много. Например, полезно иметь две или три разные сжатые версии одной и той же NP-полной задачи в качестве примеров, если сжатые кодировки имеют несколько разные формы. Не дюжина Простой способ добавить избыточность - добавить пункты в форме «Также завершено NEXP, если BLAH». Также приветствуются предложения вида «Остается NEXP-полным, если входной граф имеет степень не более BLAH».

Наконец, позвольте мне добавить личные предпочтения. Меня больше всего интересуют полные проблемы "алгебраического" аромата, если таковые имеются. Например, моя любимая проблема # P-complete - это перманент из-за ее алгебраического вида. Я надеюсь, что равенство NEXP = MIP также может обеспечить некоторую хорошую алгебраическую проблему, полную NEXP, о которой я не знаю.

слитон
источник
2
Сообщество вики!
Дейв Кларк
Как превратить его в вики сообщества?
Слитон
Отметьте сообщение для внимания модератора и попросите его сделать его CW.
Каве
5
почему NEXP? то есть почему не какой-то другой класс?
Суреш Венкат
1
Обратите внимание, что класс NEXP иногда также называют NEXPTIME. Это может показать дополнительные результаты при использовании поисковых систем.
Герман Грубер

Ответы:

26

Для некоторых NP-завершенных задач есть вариант SUCCINCT, который завершен NEXP.

Пример - УСПЕШНЫЙ ПУТЬ ГАМИЛЬТОНА:

  • Булева схема с 2 n входами и одним выходом представляет график на 2 n вершинах. Чтобы определить, существует ли ребро между вершинами i и j , закодируйте i и j в n битах и ​​передайте их конкатенацию в схему: между этими вершинами есть ребро, если выходной сигнал схемы равен true. При такой схеме существует ли путь Гамильтона в графе, представленном схемой?

Точно так же есть SUCCINCT 3SAT, SUCCINCT KNAPSACK и т. Д.

Ссылка

  • Хана Гальперин и Ави Вигдерсон (1983), «Сжатые представления графов», Информация и управление 56: 3, с. 183–198.
Гарет Рис
источник
17

См. Http://arxiv.org/abs/0905.2419 Gottesman и Irani. Это хороший пример. По сути, мы все привыкли к мысли, что удовлетворение ограничений может быть NP-полной задачей (в зависимости от геометрии и т. Д.). Однако они рассматривают ситуацию, в которой все ограничения даются заранее, и единственное, что вам разрешено варьировать - насколько велика система. Тем не менее, это оказывается все еще трудно, если вы закодируете проблему в размере системы. То есть проблема указывается путем предоставления строки из N битов, определяющей размер системы от 0 до 2 ^ N-1. Таким образом, размер системы экспоненциально больше, чем размер ввода. Они показывают, что это NEXP-завершено (и что квантовый аналог QMA_EXP-завершен).

Мэтт Гастингс
источник
15

Позвольте мне начать с канонического:

MnMn

n2n

slimton
источник
15

2

Регулярное выражение либо

  • 0
  • 1
  • ef
  • ef
  • e2

Эти выражения представляют собой множества

  • L(0)={0}
  • L(1)={1}
  • L(ef)=L(e)L(f)
  • L(ef)={abaL(e),bL(f)}
  • L(e2)=L(ee)

соответственно.

Обратите внимание, что если мы допустим звезду Клини (ноль или более копий выражения) в качестве четвертого оператора (в дополнение к объединению, конкатенации и возведению в квадрат), то проблема определения того, представляют ли два регулярных выражения разные языки, становится EXPSPACE-полной .

Л.Дж. Стокмейер, А.Р. Мейер, « Проблемы со словом, требующие экспоненциального времени », 5-й STOC, 1973.

Sadeq Dousti
источник
14

SCHÖNFINKEL – BERNAYS SAT

  • x1x2y1y2φφ

Ссылка

Гарет Рис
источник
Является ли обратное (неудовлетворительное) coNEXP-полным?
гигабайты
Я всегда думал, что логическая формула первого порядка φ без кванторов является булевой формулой. Это не? Но для булевой формулы φ она будет полна Σ ^ P_2. Могут ли переменные в формуле Шенфинкеля-Берне иметь другие значения, кроме true и false?
BeniBela
@BeniBela: Это формулы логики первого порядка, поэтому может содержать символы отношений (значение которых должно быть указано моделью). Смотрите ссылку. Если модель ограничена двумя элементами, мы имеем BINARY SCHÖNFINKEL – BERNAYS SAT, которая остается NEXP-полной . φ
Гарет Рис