1
$\begingroup$

I have two problems, CNF-SAT and CNF-UNSAT, that decide if a formula $\phi$ on Conjunctive Normal Form is satisfiable and unsatisfiable, respectively. I have already shown that CNF-SAT is $NP$-complete by showing that it is in $NP$ and then reduced SAT to CNF-SAT.

What I wonder is if it follows that CNF-UNSAT is $NP$-complete as well, seeing as the new algorithm only has to accept whenever the algorithm for CNF-SAT rejects and vice-versa, or is it not that simple?

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

What I wonder is if it follows that CNF-UNSAT is 𝑁𝑃-complete as well, seeing as the new algorithm only has to accept whenever the algorithm for CNF-SAT rejects and vice-versa, or is it not that simple?

No, it doesn't. This is because the polynomial many-one reduction that preserves membership in NP doesn't allow that operation. A Cook reduction allows you to use a SAT oracle as a subroutine and invert the result. A Karp reduction only permits you to convert one problem to another in polynomial time and then you must accept the output of the solving algorithm for the second problem unchanged. CNF-SAT and CNF-UNSAT are not in different problem classes under Cook reductions, but they are under Karp reductions, i.e. NP and co-NP.

$\endgroup$
2
  • $\begingroup$ So you're saying that CNF-UNSAT is co-NP-complete? If so, can I use that a language $A$ is NP-complete iff $\overline{A}$ is co-NP-complete to show that CNF-TAUT (decides if $\phi$ is a tautology) is NP-complete since tautology is the opposite of unsatisfiability? $\endgroup$
    – Samsam22
    Commented May 6, 2020 at 10:15
  • 3
    $\begingroup$ CNF-UNSAT is co-NP-complete. DNF-TAUT is co-NP-complete. CNF-TAUT is trivial, just as DNF-SAT is. $\endgroup$
    – Kyle Jones
    Commented May 6, 2020 at 16:57
1
$\begingroup$

It is not that simple, and does not follow from the definitions of the class $NP$.

Roughly speaking, you can convince someone a CNF formula is satisfiable by presenting a satisfying assignment for that formula.
If such an assignment exists, then an NTM could guess it.

I don't see how you can prove a formula is not satisfiable by guessing some assignment.

BTW

I'm not saying this reduction can't be done, because it is an open question, but it is not that simple.

$\endgroup$
1
  • 1
    $\begingroup$ You can show a formula is unsatisfiable by guessing the set of inference steps in some proof system which together prove a formula is unsatisfiable. The reason CNF-UNSAT hasn't been shown to be in NP is that no one knows whether there is a proof system strong enough to show unsatisfiability in a proof size polynomial to the size of the formula for all CNF formulas. No one has shown that it can't be done either. So NP = co-NP remains an open question. $\endgroup$
    – Kyle Jones
    Commented May 5, 2020 at 17:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .