Comment preuve $ {NPC \ BIGCAP CO-NPC \ NE \ NE \ VARNOTHING Puis NP= P?} $

Question

Comment la preuve $ {\ \ npc \ \ \ bigcap \ co-npc \ ne \ varnothing} $ alors $ {np= p?} $

Answer 1

Je ne pense pas que vous trouviez probablement une telle preuve.Compte tenu de notre niveau actuel de connaissances, autant que nous sachons, il est possible que $ \ textsf {p} \ ne \ textsf {np} $ mais $ \ textsf {np}=textsf {co-np} $ (nous ne pouvons pas prouver le contraire).Si c'était vrai, alors nous aurions $ \ textsf {npc}=textsf {co-npc} $ (et donc $ \ textsf {npc} \ cap \ textsf {co-npc} \ ne \ videtyset $ ) ) $ \ textsf {p} \ net \ textsf {np} $ .

Voir, par exemple, est la question ouverte np= co-np identique à p= np? et si NP $ \ NEQ $ CO-NP est alors P $ \ NEQ $ NP .