كيفية إثبات P= NP إذا مشكلة π ε np-complete والمشكلة تكمل πc ε np؟

Question

كيفية إثبات إذا P= NP إذا مشكلة π ε np-complete والمشكلة تكمل πc ε np؟ أو P= NP إذا تتقاطع NPC مع CO-NPC

Answer 1

proving $ NP= CO-NP $ لا يعني بالضرورة أن $ p= np $ وبعدعلى الرغم من أنه، فإن الطريقة الأخرى حول هو صحيح: افترض $ p= np $ ، ثم $ co-np= co-p= p= p= np= np $ .

Answer 2

لن تجد أي شيء مفيد مع معرفتنا الحالية.ومع ذلك، تغيير إلى $ \ pi ^ c \ {mbox {p} $ سوف تحصل على $ \ mbox {p}=Mbox {np} $ .