Может ли NP-Intermediate существовать, если P = NP? - PullRequest
3 голосов
/ 12 апреля 2010

Насколько я понимаю, теорема Ладнера в основном такова:

P! = NP означает, что существует набор NPI, где NPI не находится в P и NPI не является NP-завершенным

Что произойдет с этой теоремой, если мы предположим, что P = NP, а не P! = NP? Мы знаем, что если NP Intermediate не существует, то P = NP. Но может ли NP Intermediate существовать, если P = NP?

Ответы [ 4 ]

3 голосов
/ 12 апреля 2010

NPI должен подразумевать, что он находится в NP, но не NP-завершен.

Если P = NP, то все проблемы в P и NP будут NP-полными, потому что любая проблема будет сводиться к другой за полиномиальное время (∅ и Σ * не могут быть NP-полными, потому что мы не можем отобразить произвольная проблема для любого из них - у нас не будет ничего для сопоставления для положительного / отрицательного случая. Однако, так как они находятся в P, мы не заботимся о них для цели этого вопроса.)

Поскольку все проблемы в NP являются NP-полными, NPI не может существовать.

3 голосов
/ 12 апреля 2010

Вы пропустили одно свойство NPI: Каждый элемент NPI находится в NP (но не в P). Это явно невозможно, если P = NP, поэтому, если P = NP, NPI должен быть пустым.

2 голосов
/ 12 апреля 2010

Если P = NP, то NPI не может существовать, предполагая, что это подмножество NP, так как все NP находятся в P, и, следовательно, часть «не в P» определения NPI не будет иметь места ни для какой проблемы. Так что в этом случае класс NPI будет пустым.

1 голос
/ 03 мая 2014

Теорема Ладнера в ее классической формулировке ничего не говорит о случае, когда P = NP.

Из базовой логики $ A \ rightarrow B $ ничего не говорит о $ not (A) $ ... к сожалению.

Кроме того, если $ P = NP $ и $ NP $ сводится к Куку к $ NP-полному $ ... тогда это будет означать, что большинство задач, которые мы вычисляем в вычислениях (сложение, преобразования Фурье, сортировка), сводимы скажем, к сумме подмножеств .... при условии, что теорема Кука верна Это было бы довольно изнурительным.

Но из теоремы Ладнера мы можем просто сказать что-нибудь о случае $ P = NP $.

...