Unique SAT is in DP

Question

I am an engineer learning about the complexity class DP, and I am looking at a number of sources that mention that UNIQUE-SAT and CRITICAL-SAT are both in DP. Is there a proof of this fact somewhere that I can learn from?

Answer 1

Just use the definition: $\phi$ is in UNIQUE-SAT if and only if $$\underbrace{\phi\in\mathrm{SAT}}_{\text{NP property}}\text{ and not }(\underbrace{\text{$\phi$ has at least two satisfying assignments}}_{\text{NP property}}).$$

Likewise: a CNF $\phi=\bigwedge_{i<n}C_i$ is in CRITICAL-SAT if and only if $$\Bigl(\underbrace{\text{$\bigwedge_{i\ne j}C_i$ is satisfiable for each $j$}}_{\text{NP property}}\Bigr)\text{ and not }\underbrace{\phi\in\mathrm{SAT}}_{\text{NP property}}.$$ To see that the property in brackets is in NP, it can be witnessed by a sequence of $n$ assignments, where the $j$th assignment satisfies all clauses except $C_j$.

Answer 2

They are defined and proved to be in $D^P$ in the original article by Papadimitriou and Yannakakis, The complexity of facets (and some facets of complexity) published in JCSS in 1984 (Volume 28, Issue 2, April 1984, Pages 244-259).

Critical-SAT is defined in a follow-up article by Papadimitriou and Wolfe The complexity of facets resolved published in JCSS in 1988 (Volume 37, Issue 1, August 1988, Pages 2-13).

---

The complexity class $D^P$ is essentially languages that are the intersection of a language in $\text{NP}$ and a language in $\text{co-NP}$.

A couple of $D^P$-complete problems:

• SAT-UNSAT: Input is two SAT formulae $\Phi_S$ and $\Phi_U$ and the question is whether $\Phi_S$ is satisfiable and $\Phi_U$ is unsatisfiable.

• Minimal unsatisfiability: Input is a 3-CNF-SAT formula $\Phi$. Question: Is it true that $\Phi$ is unsatisfiable, but removing any clause at all makes the resulting formula satisfiable?

• Exact clique: Input is a graph $G$ and an integer $k$. Question: Does the largest clique in $G$ have size $k$?

• Critical clique: Input is a graph $G$ and an integer $k$. Question: Is it true that $G$ does not have a $k$-clique, but if you add any edge at all, then the resulting graph will have a $k$-clique?

• Maximum non-hamiltonian graph: Input is a graph $G$. Question: Is it true that $G$ is non-hamiltonian but adding any edge at all to graph results in a hamiltonian graph?

• Minimal 3-colorability: Input is a graph $G$. Question: Is it true that $G$ is not 3-colorable, but deleting any vertex at all results in a 3-colorable graph?