如何证明p= np如果问题πεnp-complete and问题补充πcεnp？

Question

如何证明p= np如果问题πεnp-complete and问题补充πcεnp？ 或者 如果NPC与CO-NPC相交，则P= NP

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} $ 。