كيفية الإثبات $ {npc \ bigcap co-npc \ ne \ ne \ parnothing ثم np= p؟} $

Question

كيف إثبات $ {\ \ npc \ \ \ bigcap \ \ co-npc \ ne \ parnothing} $
ثم $ {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} \ ne \ ne \ emptyset $ ) حتى الآن $ \ textsf {p} \ Ne \ textsf {np} $ .

انظر، على سبيل المثال، هو السؤال المفتوح NP= CO-NP نفس P= NP؟ و إذا كان NP $ \ NEQ $ CO-NP إذن P $ \ NEQ $ NP .