1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – Raphael Mar 16 '16 at 10:23
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ That's my suggestion. There might be other ways to solve this exercise. $\endgroup$ – Yuval Filmus Mar 16 '16 at 16:40
  • $\begingroup$ can you give me example where a 4cnf would be unique? $\endgroup$ – user270494 Mar 16 '16 at 16:48
  • 1
    $\begingroup$ No. I'm not going to solve the exercise for you. I believe you can come up with a 4CNF that has a unique satisfying assignment on your own. I suggest you spend a few hours on this exercise before giving up. When you're just starting, these exercises can be difficult, but they get easier with time. $\endgroup$ – Yuval Filmus Mar 16 '16 at 16:53
  • $\begingroup$ 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 $\endgroup$ – user270494 Mar 16 '16 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.