Как доказать p= np, если проблема Π ε NP-полная и проблема дополнения πc ε NP?
-
29-09-2020 - |
Вопрос
Как доказать, если P= NP Если проблема π ε NP-полная и проблема дополнения πc ε NP? ИЛИ ЖЕ P= NP Если NPC пересекается с CO-NPC
Решение
Доказательство $ np= co-np $ не обязательно означает, что $ p= np $ ОтказХотя, наоборот это правильно: Предположим, $ p= np $ , затем $ co-np= co-p= p= np $ .
Другие советы
Вы не найдете ничего полезного с нашими текущими знаниями.Тем не менее, изменение $ \ pi ^ c \ in \ mbox {p} $ получит вам $ \ mbox {p}=Mbox {NP} $ .
Не связан с cs.stackexchange