A version of SAT

Question

How can I prove that there isn't any polynomial Turing Machine that by given a CNF formula $\ \phi$ and an assignment $\ \tau$ , it returns an assignment $\ \tau '$ such that $\ \tau \ne \tau '$? thanx!

Answer 1

If there was a Turing machine T that could do this (assuming another $\tau'$ exists), you could modify it to find a satisfying assignment for any CNF formula that has one. Namely, suppose you are given CNF formula $\phi = C_1 \wedge \ldots \wedge C_m$ in variables $x_1, \ldots, x_n$. Using a new variable $x_0$, apply your Turing machine to the CNF formula

$$ (x_0 \vee C_1) \wedge \ldots \wedge (x_0 \vee C_m) \wedge (\neg x_0 \vee x_1) \wedge \ldots \wedge (\neg x_0 \vee x_n) $$

with $\tau = (\text{true}, \ldots, \text{true})$.
Note that $\tau$ is a satisfying assignment. Any other satisfying assignment $\tau'$ will have $x_0$ false and $\phi(x_1, \ldots, x_n)$ true.

Of course, you're not really proving "there isn't any polynomial Turing machine ...", because you don't know whether $P=NP$. If $P=NP$, such a machine does exist.

Answer 2

You mean to prove that the following problem is NP-hard:

Input: CNF formula $\phi$ over $n$ variables $x_1, \dots, x_n$, and an assignment $\tau : \{1,\dots, n\} \to \{0,1\}$ s.t. $\phi[\tau] = 1$.

Output: $\tau' : \{1, \dots, n\} \to \{0,1\}$ s.t. $\tau' \neq \tau$ and $\phi[\tau'] = 1$, or "FAIL" if no such $\tau'$ exists.

Let's call this problem USAT ("Unique SAT"). Karp reduce from SAT (which is itself NP-hard):

On instance $\psi$ of SAT, take a new variable $z$ and transform each clause $C$ to $C\vee z$. Also stick on (the CNF form of) $\neg z \vee (x_1 \wedge x_2 \wedge x_3 \wedge \cdots \wedge x_n)$.

Call this formula $\psi'$. A satisfying assignment is $z = 1, x_i = 1$ for every $i$. Let's call that assignment $\tau$. The instance of USAT is $(\psi', \tau)$.

You should check that $\psi'$ has another satisfying assignment different from $\tau$ iff $\phi$ has a satisfying assignment.