On the unique satisfiability problem

Abstract

UNIQUE SAT is the problem of deciding whether a given Boolean formula has exactly one satisfying truth assignment. This problem is a typical (moreover complete) representative of a natural class of problems about unique solutions. All these problems belong to the class DIFP = L1 L2:L1, L2 [epsilon] NP studied by Papadimitriou and Yannakakis. We consider the relationship between these two classes, particularly whether UNIQUE SAT is DIFP-complete: It is if NP = co NP. We construct an oracle relative to which UNIQUE SAT is not complete for DIFP, and another oracle relative to which UNIQUE SAT is complete for DIFP, whereas NP [not equal to] co NP.