NP-Hard проблемы, которые не в NP, но разрешимы

31

Мне интересно, есть ли хороший пример для простой для понимания проблемы NP-Hard, которая не является NP-Complete и не неразрешима?

Например, проблема остановки - NP-Hard, а не NP-Complete, но неразрешима.

Я считаю, что это означает, что это проблема, решение которой можно проверить, но не за полиномиальное время. (Пожалуйста, исправьте это утверждение, если это не так).

себя
источник
Беглый взгляд на зоопарк сложности делает этот вопрос почти глупым - между NP и R просто так много классов ! Конечно, мы не знаем, чтобы все включения были строгими, поэтому здесь есть кое-что интересное.
Рафаэль

Ответы:

33

По недетерминированной версии теоремы об иерархии времени мы имеем , где \ mathsf {NEXP} - это класс задач, разрешимых в недетерминированном экспоненциальном времени. Таким образом, достаточно рассмотреть любую проблему, которая является \ mathsf {NP} -hard и в \ mathsf {NEXP} , но не в \ mathsf {NP} . Например, мы можем рассмотреть любую \ mathsf {NEXP} -полную проблему , такую ​​какNPNEXPNEXPН Е Х П Н П Н Е Х ПNPNEXPNPNEXP

  • 3-окрашиваемость графов, описываемых лаконичными схемами, или любая другая NP-полная задача на графах, где «лаконичная схема» - это формат для представления очень больших графов на входе: вместо явного представления графа, например  , списками смежности, вместо этого мы предоставляем схему, вычисляющую некоторую функцию f:{0,1}n×{0,1}n{0,1} которая вычисляет коэффициенты для 2n×2n матрица смежности.

  • (Не) эквивалентность двух регулярных выражений, где звезда Клини заменяется квадратом (повторение подшаблонов ровно дважды, а не ноль или более раз), и где мы спрашиваем, представляют ли два таких регулярных выражения разные наборы строк.

Обратите внимание, что в последнем случае, если мы возьмем регулярные выражения, как мы привыкли рассматривать, в том числе звезду Клини, результирующая проблема будет иметь вид -complete: потому что у нас есть контейнеры , это все еще решаемая проблема, которая -hard, а не в .N PN E X PE X P S P A C E N P N PEXPSPACENPNEXPEXPSPACENPNP

Ниль де Бодрап
источник
7

Отказ от ответственности: Этот ответ основан на предположении, что , гипотеза, в которую большинство ученых твердо верят, но нам еще предстоит доказать. Это означает, что существует вероятность того, что эти проблемы находятся в и, таким образом, также -полные.НП НПPSPACENPNPNP

Я бы сказал, что наиболее простыми являются Истинная квантифицированная логическая формула и Обобщенная география , обе из которых -complete.PSPACE

TQBF получает количественную булеву формулу, проверяет, является ли формула истинной, то есть формулы в форме - false, потому что установка в false приводит к ложному утверждению.zxyz.[(xy)z]z

Generalized Geography - это забавная игра (см. Цепочку слов ), в которой у вас есть список строк (например, названия городов), и игрок 1 начинает с произнесения имени, а игрок 2 отвечает именем, начинающимся с той буквы, с которой закончилось предыдущее имя. Затем наступает очередь Игрока 1, пока кто-нибудь не застрянет (эту игру рекомендуется играть как пьющую игру, где объектами являются группы / художники, фильмы, города, столицы, известные математики или кто-то еще, кто плывет на вашей лодке. Тот, кто не может ответить в течение разумного времени надо конечно пить). Формальная проблема сформулирована как вопрос «есть ли у Игрока 1 выигрышная стратегия» .

Пол Г.Д.
источник
9
Я не думаю , что этот ответ не подходит, так как есть классы , которые мы сделать знаем строго выше NP , который может служить. По крайней мере, вы должны пересмотреть свой ответ так, чтобы вместо вашего постскриптума в конце вы могли сказать вместо этого в начале вашего ответа, что ваш ответ зависит от ( неравенство, в котором мы убеждены, вероятно, верно). --- Этот комментарий заменяет комментарий, который я удалил ранее; извините за спам. NPPSPACE
Ниль де Боудрап