How to prove P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP?
-
29-09-2020 - |
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
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