Как доказать p= np, если проблема Π ε NP-полная и проблема дополнения πc ε NP?

Question

Как доказать, если P= NP Если проблема π ε NP-полная и проблема дополнения πc ε NP? ИЛИ ЖЕ P= NP Если NPC пересекается с CO-NPC

Answer 1

Доказательство $ np= co-np $ не обязательно означает, что $ p= np $ ОтказХотя, наоборот это правильно: Предположим, $ p= np $ , затем $ co-np= co-p= p= np $ .

Answer 2

Вы не найдете ничего полезного с нашими текущими знаниями.Тем не менее, изменение $ \ pi ^ c \ in \ mbox {p} $ получит вам $ \ mbox {p}=Mbox {NP} $ .