TAOCP 7.2.2.2 Exercise 427
The needed solution depends on the precise function from 7.
Section 7.2.2.2: Satisfiability
Exercise 427. [M30] Exhibit a function $f(x_1, \ldots, x_n)$ for which every set of forcing clauses that uses no auxiliary variables has size $\Omega(3^n/n^2)$, although $f$ can actually be represented by a polynomial number of forcing clauses when auxiliary variables are introduced. Hint: See exercise 7.1.1–116.
Verified: no
Solve time: 9m16s
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.