Может ли NP-Intermediate существовать, если P = NP?
Насколько я понимаю, теорема Ладнера в основном такова:
P! = NP означает, что существует набор NPI, где NPI не находится в P, а NPI не является NP-завершенным
Что произойдет с этой теоремой, если мы предположим, что P = NP, а не P! = NP? Мы знаем, что если NP Intermediate не существует, то P = NP. Но может ли NP Intermediate существовать, если P = NP?
4 ответа
NPI должен подразумевать, что он находится в NP, но он не NP-завершен.
Если P = NP, то все задачи в P и NP будут NP-полными, потому что любая задача будет сводиться к другой за полиномиальное время (∅ и Σ* не могут быть NP-полными, потому что мы не можем отобразить произвольную задачу к любому из них - у нас не будет ничего для сопоставления для положительного / отрицательного случая. Однако, поскольку они находятся в P, мы не заботимся о них для цели этого вопроса.)
Поскольку все проблемы в NP являются NP-полными, NPI не может существовать.
Вы пропустили одно свойство NPI: каждый элемент NPI находится в NP (но не в P). Это явно невозможно, если P=NP, поэтому, если P=NP, NPI должен быть пустым.
Если P=NP, то NPI не может существовать, предполагая, что это подмножество NP, поскольку все NP находятся в P, и, следовательно, часть "не в P" определения NPI не будет иметь места ни для какой проблемы. Так что в этом случае класс NPI будет пустым.
Теорема Ладнера в ее классической формулировке ничего не говорит о случае, когда P=NP.
Из базовой логики, $A\rightarrow B$ ничего не говорит о $not(A)$... к сожалению.
Кроме того, если $P=NP$ и $NP$ сводится к Куку к $NP-полному $... тогда это будет означать, что большинство задач, которые мы вычисляем в вычислениях (сложение, преобразования Фурье, сортировка), сводятся, скажем, к, сумма подмножеств.... при условии, что теорема Кука верна. Это было бы довольно изнурительным.
Но из теоремы Ладнера мы можем просто сказать что-нибудь о случае $P=NP$.