TAOCP 7.2.2.2 Exercise 252
Exercise 252 depends on the precise form of the anti-maximal-element clauses (99)–(101) and on the definition of variable elimination and subsumption from Section 7.
Section 7.2.2.2: Satisfiability
Exercise 252. [M26] Can the unsatisfiability of (99)–(101) be proved in polynomial time by repeatedly performing variable elimination and subsumption?
Verified: no
Solve time: 1m31s
Setup
Exercise 252 depends on the precise form of the anti-maximal-element clauses (99)–(101) and on the definition of variable elimination and subsumption from Section 7.2.2.2. The supplied context includes only the earlier discussion through equation (8), so the clauses (99)–(101) themselves are not available.
The question asks whether the specific unsatisfiability proof for those clauses can be obtained in polynomial time by repeatedly applying two particular transformations, variable elimination and subsumption. The answer requires analyzing the structure of the clauses in (99)–(101), because the effect of elimination and subsumption depends on the variables appearing in those clauses and on the sizes of the intermediate clause sets.
Solution
A rigorous proof cannot be derived from the supplied material. The missing equations (99)–(101) determine the family of clauses being transformed, and different clause families can behave differently under repeated variable elimination and subsumption.
To answer the exercise, one must start with the anti-maximal-element clauses, apply variable elimination to suitable variables, simplify the resulting clauses by subsumption, and prove either that the resulting sequence reaches the empty clause within polynomially many operations or that some obstruction prevents such a polynomial-time derivation.
The required argument must include a bound on the number and size of intermediate clauses produced during the elimination process. Without equations (99)–(101), neither the eliminated variables nor the possible intermediate clause counts can be determined.
Verification
The requested conclusion concerns a particular SAT instance rather than a general property of variable elimination and subsumption. The omitted clause definitions are therefore necessary data for the proof.
No valid polynomial-time bound, nor a proof that such a bound is impossible for this instance, can be established from the excerpt provided.
Notes
The previous exercise 251 concerns Algorithm I with specially chosen branching and resolution steps. Exercise 252 asks about a different proof method, namely repeated variable elimination and subsumption. The relationship between the two methods depends on the exact anti-maximal-element construction.
The complete solution requires the text of equations (99)–(101) and the surrounding discussion defining the anti-maximal-element clauses.