Может ли NP-промежуточное соединение существует, если p = np?

Question

Мое понимание в том, что теорема Лэднера в основном это:

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

Answer 4

Теорема Ladner в своей классической формулировке ничего не говорит о том случае, где p = np.

От базовой логики, $ a prightarrow b $ не говорит о чем-либо о долларах (а) $ ... к сожалению.

Кроме того, если $ p = np $ и $ np $ ì cook - сводим до $ np-complete $ ... Тогда это будет означать, что большинство проблем, которые мы вычисляем в вычислениях (дополнение, преобразования Фурье, сортировка), являются сводимыми для говорящих , сумма подмножества ... Предполагая, что теорема повара действует. Это было бы вполне разумно.

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