CNF unsatisfiability NP-complete?

1k Views Asked by At

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?

2

There are 2 best solutions below

2
On BEST ANSWER

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.

1
On

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.