Есть ли проблемы NP, не в P и не в NP Complete?

34

Есть ли известные проблемы в (а не в P ), которые не являются N P Complete? Насколько я понимаю, в настоящее время нет известных проблем, когда это так, но это не исключено как возможность. NппNп

Если есть проблема , которая является (а не Р ) , но не Н Р - с о м п л е т е , это было бы результатом не существующего изоморфизма между экземплярами этой проблемы и N Р - гр о м р л е т е множество? Если этот случай, как бы мы знаем , что N P проблема не является «тяжелее» , чем то , что мы в настоящее время определить , как N P - гр уплотнительного т р л х тNппNп-сомпLеTеNп-сомпLеTеNп множество?Nп-сомпLеTе

vpiTriumph
источник
1
Смотрите также этот связанный вопрос .
Рафаэль

Ответы:

25

Есть ли известные проблемы в NP (а не в P), которые не являются NP Complete? Насколько я понимаю, в настоящее время нет известных проблем, когда это так, но это не исключено как возможность.

Нет, это неизвестно (за исключением тривиальных языков и Σ , эти два не являются полными из-за определения сокращений многие-один, обычно эти два игнорируются при рассмотрении сокращений многие-один). Существование проблемы N P, которая не является полной для N P по сравнению с многочленным сокращением времени за полином, подразумевает, что PN P, что неизвестно (хотя широко считается). Если эти два класса отличаются , то мы знаем , что существуют проблемы в N P , которые не являются полными для него, принимать какие - либо проблемы в P .ΣNPNPPNPNPP

Если существует проблема, которая представляет собой NP (а не P), но не NP Complete, будет ли это результатом отсутствия существующего изоморфизма между экземплярами этой проблемы и NP Complete?

Если два класса сложности различны , то по теореме Ладнер в существуют проблемы , которые являются -intermediate, то есть они находятся между P и N Р - с о т р л е т е .NPPNP-complete

Если в этом случае, как мы узнаем, что проблема NP не «сложнее», чем то, что мы в настоящее время определяем как полный комплект NP?

Они по - прежнему полиномиальное время сводится к проблем , поэтому они не могут быть сложнее , чем N Р - с о т р л е т е проблем.NP-completeNP-complete

Кава
источник
Прошло несколько лет, но у меня сложилось впечатление, что проблемы NP-Hard соответствуют описанию ОП, куда они вписываются?
Кевин
2
@Kevin: Нет, NP-hard означает, что проблема, по крайней мере, так же сложна, как и самые сложные проблемы в NP.
Гек Беннетт
Как насчет проблем с псевдо-полиномиальным временем выполнения?
Джо,
@ Джо, я не уверен, что ты имеешь в виду, если у вас есть вопрос, опубликуйте его как новый вопрос.
Каве
1
О, конечно, предполагая, что P! = NP. Такой проблемой был бы изоморфизм графов, верно?
Леви
11

Как сказал @Kaveh, этот вопрос интересен, только если предположить, что ; остальная часть моего ответа принимает это как предположение и в основном содержит ссылки для дальнейшего снижения аппетита. При этом предположении по теореме Ладнера мы знаем, что существуют проблемы, которых нет ни в P, ни в N P C ; эти проблемы называются N P -intermediate или N P I . Интересно, что теорема Ладнера может быть обобщена на многие другие классы сложности для получения аналогичных промежуточных задач. Далее, из теоремы также следует, что существует бесконечная иерархияпNппNпСNпNпяпромежуточных проблем, которые не являются поли-время приводимым друг с другом в .Nпя

К сожалению, даже с предположением очень трудно найти естественные задачи, которые были бы доказуемо N P I (конечно, у вас есть искусственные проблемы, вытекающие из доказательства теоремы Ладнера). Таким образом, даже если предположить, что P N P в это время, мы можем только верить некоторым проблемам, что N P I, но не доказать это. Мы приходим к таким убеждениям, когда у нас есть разумные доказательства того, что проблема N P не в N P C и / или не в PPNPNPIPNPNPINPNPCP; или просто когда его изучали в течение длительного времени и избегали вписываться в любой класс. В этом ответе есть довольно полный список таких проблем . Он включает в себя такие постоянные фавориты, как факторинг, дискретный лог и граф-изоморфизм.

Интересно, что некоторые из этих проблем (в частности, факторинг и дискретный лог) имеют полиномиальное время решения на квантовых компьютерах (то есть они находятся в ). Некоторые другие проблемы (такие как граф-изоморфизм), как известно, не находятся в B Q P , и есть продолжающиеся исследования, чтобы решить вопрос. С другой стороны, есть подозрение, что N P C B Q P , поэтому люди не верят, что у нас будет эффективный квантовый алгоритм для SAT (хотя мы можем получить квадратичное ускорение); это интересный вопрос, чтобы беспокоиться о том, какая структура N P I проблемы нужны для того, чтобы быть в BBQPBQPNPCBQPNPIBQP .

Артем Казнатчеев
источник
Действительно недавний результат Бабая (см. Jeremykun.com/2015/11/12/… ) дает квазиполиномиальный алгоритм для изоморфизма графа, в основном удаляя его из NPI, если результат верен. Интересно, что это была проблема, которая не была известна в BQP
Фредерик Гроссханс
1
@ FrédéricGrosshans, имеющий алгоритм квазиполиномиального времени, не удаляет вас из NPI (фактически, он даже не удалит вас из NPC, если вы не сделаете более сильные предположения, чем просто P! = NP). Результат Бабая (если он правильный, что, вероятно, так и есть) дает лишь косвенные доказательства того, что GraphIso может быть в P, поскольку в прошлом, когда были найдены квазиполиномиальные алгоритмы для сложных задач, они в конечном итоге приводили к полиномиальным алгоритмам.
Артем Казнатчеев
1
@ FrédéricGrosshans Babai отказался от требования квазиполиномиального времени выполнения . Видимо была ошибка в анализе.
Рафаэль
@ Рафаэль за мой предыдущий комментарий, я не думаю, что Бабай, переводящий квазиполиномиальное в субэкспоненциальное, не имеет особого отношения к обсуждению.
Артем Казнатчеев
Поскольку этот комментарий все еще здесь, я не хотел, чтобы он оставался без исправлений. (По сути, я отследил все вхождения «Babai» на сайте и опубликовал один и тот же комментарий.) Не стесняйтесь отмечать все комментарии, чтобы они считались устаревшими.
Рафаэль
7

Нет NP -полных проблемы , как известно, в P . Если для какой-либо задачи с NP- полным существует алгоритм за полиномиальное время , то P = NP , потому что любая проблема в NP имеет сокращение за полиномиальное время до каждой задачи с NP- полным. (Это на самом деле то, как определяется « NP- полный».) И, очевидно, если каждая проблема NP- полного находится за пределами P , это означает, что PNP . Мы не совсем уверены, почему трудно показать это так или иначе; если бы мы знали ответ на этот вопрос, мы, вероятно, знали бы намного больше о P иNP . У нас есть несколько методов доказательства, которые, как мы знаем, не работают (например, релятивизация и естественные доказательства), но у нас нет принципиального объяснения того, почему эта проблема сложна.

Если в NP есть проблемы, которых нет в P , то фактически существует бесконечная иерархия проблем в NP между задачами в P и теми, которые являются NP- полными: это результат, называемый теоремой Ладнера .

Надеюсь это поможет!

templatetypedef
источник
пожалуйста, объясните: нет никаких проблем в NP, как известно, не в P? Разве не все P уже в NP?
1
@ Shimano - это две разные концепции: все проблемы в P, как известно, находятся в NP. Тем не менее, мы не знаем, есть ли какие-либо проблемы в NP не в P. То есть мы знаем, что P является подмножеством NP, но мы не знаем, является ли NP подмножеством P. Это проясняет ситуацию?
templatetypedef
Теперь все становится яснее. Большое спасибо за ваши быстрые ответы. Нужно еще одно уточнение. Вы сказали: «Причина этого в том, что любая проблема в NP имеет сокращение за полиномиальное время до каждой задачи, полной NP». Это доказывает, что все проблемы в NP автоматически завершены? Я снова немного растерялся
@ Шимано: Не совсем. Направление сокращения важно. Проблема является NP-полной, если все проблемы в NP сводятся к этой проблеме. Вы также можете показать, что проблема NP-сложная, уменьшив известную проблему NP-complete до этой проблемы. Однако демонстрация того, что проблема в NP сводится к известной проблеме NP-полной, не показывает ничего нового, поскольку по определению все проблемы NP сводятся ко всем задачам с NP-полной.
templatetypedef
1
@ Теорема Шимано - Ладнера гласит, что если P! = NP, то должны быть NP-промежуточные задачи, поэтому, если нет NP-промежуточных задач, то P = NP. И да - если мы можем найти проблему в NP, которой нет в P, независимо от того, находится ли она в BQP, тогда P! = NP.
templatetypedef
5

Есть некоторые проблемы, которые являются NP, но никто не знает, что они являются NP-полными или , как изоморфизм графов 1 . Но, как я знаю, для таких проблем не существует специального класса сложности, может быть, я ошибаюсь.P

Может быть, это , например, до алгоритма AKS никто не знает, что тестирование простоты - это P или NPC.PP

P


1 Аналогичная проблема: изоморфизм подграфа является NP-полным в сильном смысле.


источник
Спустя 3 года граф-изоморфизм кажется очень близким к P (алгоритм квазиполинейного времени был предложен Бабаи) jeremykun.com/2015/11/12/…
Фредерик Гроссханс
Ошибка в доказательстве Бабая была исправлена ​​через несколько дней.
Дэвид Беван