Is it possible that Co-NP = P but NP != P
-
29-09-2020 - |
Question
Suppose there exists an algorithm that takes as input an unsatisfiable SAT formula, and never fails to verify it in polynomial time. However, when the input is a satisfiable formula, it doesn't work (let's say time and memory problems, the algorithm gets lost in the reasoning).
Then Co-NP = P because we can verify unsatisfiable instances in polynomial time. The certificate of unsatisfiability is the formula itself.
But then is it still possible that P != NP?
Solution
If co-$\mathsf{NP} = \mathsf{P}$ then $\mathsf{NP} = \text{co-}\mathsf{P} = \mathsf{P}$.
OTHER TIPS
The answer is no, and the reason is that $\mathrm{P}$ is trivially closed under complement. Just by definition of $\mathrm{co}$, it follows that $\mathrm{coNP} = \mathrm{P}$ is equivalent to $\mathrm{NP} = \mathrm{coP}$, and then we use that $\mathrm{coP} = \mathrm{P}$ to conclude that $\mathrm{coNP} = \mathrm{P}$ iff $\mathrm{NP} = \mathrm{P}$.
Let X be any problem in NP, which means there is a simple proof whenever the answer is YES. Now take the problem X’: “Does X have the answer NO”. That’s in co-NP, so it would be in P, therefore X isin P.