$ {NPC \ BIGCAP CO-NPC \ NE \ varnothing \ NP= Pを証明する方法$

Question

プルーフ $ {\ \ npc \ \ \ bigcap \ \ co-npc \ Ne \ varnothing} $ $ {np= p？$

Answer 1

そのような証明を見つける可能性があるとは思わない。現在の知識レベルを考えると、 $ \ textsf {p} \ ne \ textsf {np} $ が $ \ textsf {np}=textsf {co-np} $ （それ以外の場合は証明できません）。それが真だった場合、 $ \ textsf {npc}=textsf {co-npc} $ （そして $ \ textsf {npc} \ cap \ textsf {co-npc} \ eaptyset $ ）まだ $ \ textsf {p} \ ne \ textsf {np$ 。

例えば、は、P= NP？と同じというオープン質問NP= CO-NPです。 NP $ \ NEQ $ CO-NPの場合はP $ \ NEQ $ NP