The Theory of Computation

Bernard M.E. Moret

Addison-Wesley-Longman, 1998


Detailed Solutions

Chapter 7, Problem 7.45




Interestingly, the obvious symmetric counterpart of this statement is not known to hold: that is, we do not know whether Unique Satisfiability can be in coNP without forcing NP=coNP.

Assume that Unique Satisfiability is in NP. Then it has a concise certificate, which attests not only to the satisfiability of the instance, but also to the fact that it cannot be satisfied in more than one way. We want to show that Unsatisfiability is then in NP. Given an instance of Unsatisfiability, we transform it into an instance of Unique Satisfiability as follows. Denote the instance of Unsatisfiability, a Boolean expression over the variables {x1,...,xn}, by E; set all variables to true and evaluate E, then evaluate E. If the result is true, we have a "no" instance of Unsatisfiability and map it to a fixed "no" instance of Unique Satisfiability, say the instance composed of one clause over two variables, {x1,x2}. Otherwise, set up E'=E union {alpha, not alpha}, where alpha does not appear in E. Then, if E has a satisfying truth assignment, E' has two, since the value of alpha is indifferent.

Otherwise, consider the new expression

(x1 => E') and (x2 => E') and ... and (xn => E') and (alpha => E')

Suppose that E cannot be satisfied; then this new expression can only be satisfied by setting every xi and alpha to false (since then the implications are all of the type "false implies false", which is true). Thus the satisfying truth assignment for the new instance is unique. If E can be satisfied, then there are several ways in which we can satisfy the new expression: we can still assign "false" to all variables, but we can also assign a satisfying truth assignment for E -- in which case every implication is either "false implies true" or "true implies true", both of which are true. Thus we have the desired result: the new expression is uniquely satisfiable if and only if the original is unsatisfiable. Note that, interestingly, the new expression is always satisfiable: the tricky part is the uniqueness.

The new expression can be constructed in polynomial time: each term in it is of the form x => E, or (not x) or E; the logical OR distributes over the clauses simply by adding the literal not x inside each clause of E. Thus we effectively get n+1 copies of the collection E, where each clause has been augmented by one literal. This is easily carried out in polynomial (at most quadratic) time.

Thus we have a many-one polynomial-time reduction from the coNP-complete problem Unsatisfiability to Unique Satisfiability. If the latter is in NP, it follows immediately from (the converse of) Exercise 7.9 that we must have NP=coNP.