# Reducing co3SAT to UNIQUE-SAT

I am having trouble with this problem:

Let N3SAT denote the non-satisfiability problem for 3CNF’s. Show that $N3SAT\leq_p UNQ$ where in UNQ, given a CNF φ we want to know whether there is a unique satisfying assignment for φ.

I am given a hint that for every 3CNF ψ, I should construct a CNF φ (in polytime) such that ψ is a NO input for 3SAT if and only if φ is a YES input for UNQ.

What I'm having problem with is constructing the CNF from a 3CNF. Isn't a 3CNF just a case of a CNF.

So, from what I understand, once I get a CNF φ that gives a yes for UNQ, then that corresponding 3CNF will give a NO for 3SAT. So somehow the truth assignments will work out in a way that both conditions are solved.

Can someone help me out?

• The title you have chosen is not well suited to representing your question (it describes every single exercise problem of this kind). Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Mar 16 '16 at 10:23

You are right that a 3CNF is, in particular, a CNF. The hint you give suggests that you find a reduction that, given a 3CNF $\psi$ on $n$ variables, constructs a CNF $\varphi$ such that $N(\psi) = 0$ iff $N(\varphi) = 1$, where $N(\chi)$ is the number of satisfying assignments of $\chi$. I can give a stronger hint: the reduction constructs a 4CNF $\varphi$ on $n+1$ variables such that $N(\varphi) = N(\psi) + 1$.
• Ok this 4CNF $(x_1 v x_1 v x_1 v x_1)$ has a unique satisfying assignment, but the 3CNF $(x_1 v x_1 v A) N (Abar v x_1 v x_1)$ also satisfies 3SAT – user270494 Mar 16 '16 at 17:01