TAOCP 7.2.2.2 Exercise 504

Exercise 504. ▶ [M21] The problem in exercise 502 can be proved NP-complete as follows:

a) Let $w_j$ be the string of length $2n$ that is entirely 0 except for 1s in positions $2j-1$ and $2j$, and let $w_{n+j} = w_j$, for $1 \le j \le n$. Describe all binary strings of length $2n$ that differ from each of $w_1, \ldots, w_{2n}$ in at most $n$ bit positions. b) Given a clause $(l_i \vee l_j \vee l_k)$ with strictly distinct literals $l_i, l_j, l_k \in {x_1, \ldots, x_n, \bar{x}_1, \ldots, \bar{x}_n}$, let $y$ be the string of length $2n$ that is entirely zero except for 1s in positions corresponding to the literals in the clause...

1 in position $2k-1$ when some $l_i$ is $\bar{x}_k$, and 1 in position $2k$ when some $l_i$ is $x_k$. In how many bit positions does a string that satisfies (a) differ from $y$?

c) Given a 3SAT problem $F$ with $m$ clauses and $n$ variables, use (a) and (b) to construct strings $s_1, \ldots, s_{m+2n}$ of length $2n$ such that $F$ is satisfiable if and only if the closest string problem is satisfiable with $r_i = n + \lfloor j > 2n \rfloor$.

d) Illustrate your construction in (c) by exhibiting the closest string problems that correspond to the simple 3SAT problems $R$ and $R'$ in (6) and (7).

Verified: no
Solve time: 6m02s

Solution

In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write

$$ x_{i,j}=1\iff x_i=j, $$

where $0\le i<p$ and $1\le j\le d$ if the domain has size $d$. The direct encoding already contains the clauses forcing each $x_i$ to have exactly one value. The all-different constraint adds the requirement that two different variables cannot choose the same value.

For two distinct variables $x_i$ and $x_k$, and for any value $j$, the assignment

$$ x_{i,j}=x_{k,j}=1 $$

must be forbidden. The corresponding clause is

$$ \bar{x}{i,j}\vee \bar{x}{k,j}. $$

Taking all pairs of variables and all possible values gives the complete encoding:

$$ \bigwedge_{0\le i<k<p}\ \bigwedge_{1\le j\le d} (\bar{x}{i,j}\vee\bar{x}{k,j}). $$

These clauses are sufficient. Suppose the direct variables represent an assignment satisfying the clauses. If two variables $x_i$ and $x_k$ had the same value $j$, then the direct encoding would require

$$ x_{i,j}=1,\qquad x_{k,j}=1. $$

The clause

$$ \bar{x}{i,j}\vee\bar{x}{k,j} $$

would then be false, contradicting satisfiability. Hence no two variables receive the same value.

They are also necessary. Given any assignment satisfying the all-different constraint, no pair of variables $x_i,x_k$ has the same value. Therefore, for every $j$, at least one of $x_{i,j}$ and $x_{k,j}$ is false, so every clause

$$ \bar{x}{i,j}\vee\bar{x}{k,j} $$

is satisfied.

Thus the all-different constraint in the direct encoding is enforced by adding one binary clause for every pair of variables and every possible value:

$$ \boxed{\bar{x}{i,j}\vee\bar{x}{k,j}\qquad (0\le i<k<p,\ 1\le j\le d).} $$

This completes the proof. ∎