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?
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$.