TAOCP 7.2.2.2 Exercise 180
The statement of exercise 7.
Section 7.2.2.2: Satisfiability
Exercise 180. ▶ [25] [25] Explain how to use BDDs to compute the numbers $Q_m$ that underlie Fig. 40. What is $\max_{0 \le m \le 80} Q_m$?
Verified: no
Solve time: 36s
Solution
The statement of exercise 7.2.2.2.180 depends on definitions and data that are not included in the supplied Section 7.2.2.2 excerpt. In particular, the excerpt does not define the quantities $Q_m$, does not give the construction represented in Fig. 40, and does not specify the Boolean function or family of clauses whose BDDs are to be used.
The requested value of $\max_{0 \le m \le 80} Q_m$ cannot be derived uniquely from the material provided. Different families of BDDs can produce different sequences $Q_m$, so any numerical answer without the missing definition of $Q_m$ would be unsupported.
Please provide the portion of Section 7.2.2.2 containing Fig. 40 and the definition of $Q_m$, and the complete worked solution can then be given in the required TAOCP solution-manual style.