# Is it possible that Co-NP = P but NP != P

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?

• If $\mathsf{A}=\mathsf{B}$ then $\mathsf{coA}=\mathsf{coB}$. So if $\mathsf{coNP}=\mathsf{P}$ then $\mathsf{co(coNP)}=\mathsf{coP}$. But $\mathsf{coP}=\mathsf{P}$, and $\mathsf{co(coNP)}=\mathsf{NP}$. May 27, 2020 at 23:26

If co-$$\mathsf{NP} = \mathsf{P}$$ then $$\mathsf{NP} = \text{co-}\mathsf{P} = \mathsf{P}$$.

• What is the fundamental reason?
– user102180
May 27, 2020 at 20:53
• After thinking about it, I think one could use precise knowledge about the worst case time/memory upper bound to distinguish a 'yes' instance. Is that the reason?
– user102180
May 27, 2020 at 20:54
• Think of it this way: if co-$\mathsf{NP}=\mathsf{P}$ then for every problem $X$ in co-$\mathsf{NP}$ there is a polynomial time algorithm $A_X$ that solves $X$. Pick your favorite problem $Y \in \mathsf{NP}$. Since the complement $X$ of $Y$ is in co-$\mathsf{NP}$ you know that there is a polynomial-time algorithm $A_X$ that solves $X$. Then, there is also a polynomial-time algorithm $B$ that solves $Y$. Algorithm $B$ works as follows: it runs $A$ on the same input and then flips $A$'s answer. You have then shown that every problem in $\mathsf{NP}$ is also in $\mathsf{P}$. May 27, 2020 at 22:25
• I don't think one can take the complement "X of Y" with Y a NP problem. It's not like I could take my SAT formula, and make a new formula which is unsatisfiable, if the other is satisfiable. I think the real technical reason is the one I gave. Or maybe that the algorithm I described is not sufficient for Co-NP = P because it can always answer "YES" but never "NO" to the complementary problem.
– user102180
May 28, 2020 at 7:47
• When you take the complement of a NP problem you are not changing the instance. If the problem in NP is "Does this SAT formula $\phi$ admit a solution?" its complements is "Is it true that this SAT formula $\phi$ admits no solution?". The second problem is in co-NP (since a "no" certificate is just a satisfying assignment for $\phi$). If you have a quick algorithm $A$ for it (since co-NP=P) then you also have a quick algorithm for SAT: simply run $A$ on $\phi$ and then flip its answer. May 28, 2020 at 9:51

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.

• Is it actually possible to do this in SAT? To make a formula that is unsatisfiable if and only if another formula is satisfiable?
– user102180
May 27, 2020 at 20:53