How to prove if P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP? OR P = NP if NPC intersects with Co-NPC
$\begingroup$
$\endgroup$
-
$\begingroup$ This is a repost of a question posed 3 hours earlier. cs.stackexchange.com/questions/127453/… $\endgroup$ – Yonatan N Jun 20 at 23:02
-
$\begingroup$ Does this answer your question? Prove that if NPC ∩ co-NPC ≠ φ then NP = P $\endgroup$ – Yonatan N Jun 20 at 23:02
$\begingroup$
$\endgroup$
Proving $NP=co-NP$ doesn't necessarily mean that $P=NP$. Although, the other way around is correct: Assume $P=NP$, then $co-NP=co-P=P=NP$.
$\begingroup$
$\endgroup$
You won't find anything useful with our current knowledge. However, a change to $\Pi^c\in \mbox{P}$ will get you $\mbox{P}=\mbox{NP}$.
-
$\begingroup$ Maybe you could expand on this a bit? Won't find anything useful for what? $\endgroup$ – 6005 Jul 21 at 16:06
