On the unique satisfiability problem. (English) Zbl 0543.03027

The paper deals with UNIQUE SAT, the problem of deciding whether a given Boolean formula has exactly one satisfying truth assignment. The authors investigate the problem, whether UNIQUE SAT is \(DIF^ p\)-complete, where \(DIF^ p=\{L_ 1-L_ 2;L_ 1,L_ 2\in NP\}.\) It is shown that this problem is equivalent to the problem whether N\(P\subseteq US\), where US is the class of sets \(L\subseteq \Sigma^*\) that can be represented in the form \(L=\{x\in \Sigma^*;(\exists !y\in \Sigma^*_ 1)R(x,y)\},\) where R is a polynomial-time computable relation such that \(length(y)\leq p(length(x))\) if R(x,y) for a polynomial p. Then the relativised version of the problem is studied. The main results of the paper are the following. 1) There exists an oracle A such that \(NP^ A\not\subseteq US^ A.\) 2) There exists an oracle C such that \(NP^ C\subseteq US^ C\) and \(NP^ C\neq co-NP^ C.\)
Reviewer: M.Chytil


03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI