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?
Best Answer
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.