Como provar p= np se problema π ε np-completo e complemento de problema πc ε np?

Question

Como provar se p= np se problema π ε ε np-completo e complemento de problema πc ε np? OU P= np se o NPC intercetir com CO-NPC

Answer 1

provando $ np= co-np $ não significa necessariamente que $ p= NP $ .Embora, a outra maneira de é correta: Assumir $ p= np $ , então $ co-np= co-p= p= np $ .

Answer 2

Você não encontrará nada útil com nosso conhecimento atual.No entanto, uma mudança para $ \ pi ^ c \ in \ mbox {p} $ terá você $ \ mbox {p}=mbox {np} $ .