0
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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}$. $\endgroup$ May 27, 2020 at 23:26

3 Answers 3

-1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ What is the fundamental reason? $\endgroup$
    – user102180
    May 27, 2020 at 20:53
  • $\begingroup$ 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? $\endgroup$
    – user102180
    May 27, 2020 at 20:54
  • $\begingroup$ 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}$. $\endgroup$
    – Steven
    May 27, 2020 at 22:25
  • $\begingroup$ 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. $\endgroup$
    – user102180
    May 28, 2020 at 7:47
  • $\begingroup$ 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. $\endgroup$
    – Steven
    May 28, 2020 at 9:51
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.