Question

How to prove if P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP? OR P = NP if NPC intersects with Co-NPC

Was it helpful?

Solution

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$.

OTHER TIPS

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}$.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top