TAOCP 7.2.2.2 Exercise 428

The needed solution depends on the precise function from 7.

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.2.2.2: Satisfiability

Exercise 428. [M27] A generic graph $G$ on vertices ${1, \ldots, n}$ can be characterized by $\binom{n}{2}$ Boolean variables $Z = {z_{ij} \mid 1 \le i < j \le n}$, where $z_{ij} = [i \text{---} j \text{ in } G]$. Properties of $G$ can therefore be regarded as Boolean functions, $f(X)$.

a) Let $f_{\text{nd}}(X) = [\chi(G) \le d]$; that is, $f_{\text{nd}}$ is true if and only if $G$ has a $d$-coloring. Construct clauses $F_{\text{nd}}$ that represent the function $f_{\text{nd}}(X) \vee y$, using auxiliary variables $Z = {z_{jk} \mid 1 \le j \le n, 1 \le k \le d}$ that mean "vertex $j$ has color $k$."

b) Let $G_{\text{nd}}$ be a forcing representation of the Boolean function $F_{\text{nd}}(X, y, Z)$, and suppose that $G_{\text{nd}}$ has $M$ clauses in $N$ variables. (These $N$ variables should include the $\binom{n}{2} + 1 + nd$ variables of $F_{\text{nd}}$, along with an arbitrary number of additional auxiliaries.) Explain how to construct a monotone Boolean chain of cost $O(MN^2)$ for the function $f_{\text{nd}}$ (see exercise 7.1.2–84), given the clauses of $G_{\text{nd}}$. Note: Noga Alon and Ravi Boppana, Combinatorica 7 (1987), 1–22, proved that every monotone chain for this function has length $\exp(\Omega((n/\log n)^{1/3}))$ when $d+1 = \lfloor(n/\log n)^{2/3}/4\rfloor$. Hence $M$ and $N$ cannot be of polynomial size.

Verified: no
Solve time: 3m46s

The needed solution depends on the precise function from 7.1.1–116, because the proof must establish two separate facts:

  1. The function has $\Omega(3^n/n^2)$ prime implicants, so that every forcing representation without auxiliary variables must contain that many clauses.
  2. The same function has a polynomial-size forcing representation with auxiliary variables, usually obtained by introducing variables for intermediate circuit values and applying the forcing-clause construction.

If you provide the statement of Exercise 7.1.1–116 (or the relevant paragraph defining its function), I can write the complete TAOCP-style solution with the required lower-bound proof and auxiliary-variable construction.