← Advanced course and all videos

Video 8 of 53 · 4:19 · Foundations and representations

Choose the required answer

In this video

  1. 0:00 · Introduction
  2. 0:16 · Ask different questions of one rule
  3. 1:10 · Core explanation
  4. 2:16 · An unsatisfying point is not a failure of the solver
  5. 3:20 · A program is a way to obtain answers
  6. 4:09 · Direct takeaways

Caption transcript

Show transcript
This overview explains why one evaluated bit, a witness, a truth vector, and a reusable program are different deliverables. Comparing methods that return different artifacts can produce a misleading performance claim. Take the rule A or B and input zero one. A point query asks for one output bit, which is one. It does not request the answer for zero zero or for any other assignment. A full-vector request asks for all four bits. A witness request can ask for just one satisfying assignment, such as zero one. A full satisfying-assignment enumeration asks for all three witnesses. These outputs answer different questions even though they start from the same formula. Now project the witnesses onto A alone. The three full witnesses produce selected values zero, one, and one. Removing duplicates leaves two distinct selected answers. A full-model count of three is not the projected count of two. Choose the output before choosing the method. The same rule can be asked for one evaluated bit, one satisfying assignment, every truth output, or a reusable program. These are different deliverables. F is the exclusive-or of two results: A AND B, and C OR D. At assignment 1011, F evaluates to one. It is also a satisfying witness. A full AB-by-CD matrix contains all 16 outputs, in ascending binary order: the selected bit occupies row two, column three. A program graph instead stores operations and dependencies; it can be used to produce answers later. A witness does not contain every truth output. A graph is not the already-filled matrix. Asking how many distinct selected-variable assignments satisfy a rule is yet another contract; count each projection once even when it has several witnesses. Return to the opening two-input rule F equals A or B. This is separate from the intervening four-input example. Set A and B to zero. We will answer this one point while keeping the other assignments in mind. For the supplied point zero zero, or returns zero. That is a correct completed point answer. It does not mean the formula is unsatisfiable, because zero one, one zero, and one one still make it true. Point evaluation and existence of a satisfying assignment ask different questions. This case establishes a specific contrast. Correct point answer: 0. The complete function is still satisfiable. Keep the input, intermediate values, and conclusion together when comparing it with the previous case. The calculated answer belongs to this complete assignment under the stated rule. A compiled representation can describe how to evaluate the rule. It may be compact and reusable. That does not imply it already contains every full assignment, every selected answer, or the complete truth vector. Specify the artifact the caller actually needs before comparing methods. A fast witness is not a substitute for every truth-table output. A full table may be unnecessary when the caller only needs one decision. The example establishes a contract distinction. It does not rank all representations by speed. Any performance comparison must make both methods deliver the same required artifact and include the preparation and delivery costs relevant to that request. Name the required output before choosing a method. A witness does not replace the complete ordered truth outputs.