هل من الممكن أن CO-NP= P ولكن NP!= P

Question

لنفترض أن هناك خوارزمية تأخذ كدخل في صيغة SAT غير مرضية، ولا تفشل أبدا في التحقق من ذلك في وقت متعدد الحدود.ومع ذلك، عندما تكون الإدخال صيغة راضية، فإنه لا يعمل (دعنا نقول مشاكل الوقت والذاكرة، تضيع الخوارزمية في المنطق).

ثم CO-NP= P لأننا نستطيع التحقق من حالات غير مرضية في وقت متعدد الحدود.شهادة عدم الاستهلاك هي الصيغة نفسها.

ولكن بعد ذلك، ما زال من الممكن أن P!= NP؟

Answer 1

إذا co- $ \ mathsf {np}=mathsf {p} $ ثم $ \ mathsf {np}=text {co -} \ mathsf {p}=mathsf {p} $ .

Answer 2

الإجابة لا، والسبب هو أن $ \ mathrm {p} $ مغلقة تافهة تحت الاستكمال.فقط بحكم تعريف $ \ mathrm {co} $ ، يتبع ذلك $ \ mathrm {conp}=mathrm {p} $ يعادل $ \ mathrm {np}=mathrm {cop} $ ، ثم نستخدمها $ \ mathrm {cop}=mathrm {p} $ لاستنتاج أن $ \ mathrm {conp}=mathrm {p} $ IFF $ \ mathrm {np}=mathrm {p} $ .

Answer 3

دع x يكون أي مشكلة في NP، مما يعني وجود دليل بسيط كلما كان الجواب نعم.الآن تأخذ المشكلة X ': "هل لديك الجواب لا".هذا في CO-NP، لذلك سيكون في ف، وبالتالي X ISIN P.