TAOCP 7.2.2.2 Exercise 434
The needed solution depends on the precise function from 7.
Section 7.2.2.2: Satisfiability
Exercise 434. [21] Let $L_l$ be the language defined by the regular expression $0^10^$; in other words, the binary string $x_1 \ldots x_n$ is in $L_l$ if and only if it consists of zero or more 0s followed by exactly 1 1s followed by zero or more 0s.
a) Explain why the following clauses are satisfiable if and only if $x_1, \ldots, x_n \in L_l$: (i) $(\bar{p}_0 \vee \bar{x}0)$, $(\bar{p}0 \vee p{k-1})$ for $1 \le k \le n$, also $(\bar{p}{k-1} \vee \bar{x}_k \vee \bar{p}_k)$ ... [text truncated at page boundary]
$(q_k \vee q_{k+1})$, and $(\bar{q}{k+1} \vee x_k \vee q_k)$ for $1 \le k \le n$, also $(q{n+1})$; (iii) $(\bar{r}k \vee p{k-1}) \wedge \bigwedge_{0 \le d \le l} (\bar{r}k \vee x{k+d}) \wedge (\bar{r}k \vee \bar{r}{k+1})$ for $1 \le k \le n+1-l$, also $(r_1 \vee \cdots \vee r_{n+1-l})$.
b) Show that those clauses are forcing when $l = 1$ but not when $l = 2$.
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:
- The function has $\Omega(3^n/n^2)$ prime implicants, so that every forcing representation without auxiliary variables must contain that many clauses.
- 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.