SAT Solvers and What Makes Search Practical · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Search that learns from failure

Computing · Algorithms & Data Structures · ages 22-24
Name ______________________   Date ____________

  1. What does conflict-driven clause learning add to backtracking?

    • A polynomial running-time guarantee for every input
    • Only a different order for selecting the next variable
    • Learned clauses implied by the original formula

  2. A correct encoding expresses every rule as one or more clauses. What does a satisfying assignment establish?

    • Any one encoded rule may be ignored
    • Every encoded rule holds
    • Every variable must have the value true

  3. A SAT solver finishing quickly on selected factory-scheduling encodings disproves SAT's NP-completeness.

    Circle one:   True   False

  4. A formula contains P or Q and P or not-Q. Which unit clause is implied by these clauses and can be learned?

    • P
    • not-P
    • Q

  5. Let A mean task A is selected for a time slot, and B mean task B is selected for that same slot. At most one may be selected. Which expression encodes this rule?

    • A or B, requiring at least one task
    • not-A or not-B
    • A and B, requiring both tasks

  6. An assignment makes 99 clauses true and the remaining clause false in a 100-clause conjunctive-normal-form formula. Does this assignment satisfy the formula?

    • Yes; making most of the clauses true is enough
    • Yes; the remaining false clause can always be ignored
    • No; one false clause is enough

  7. Let M mean a data upload is complete and N mean its report is complete. A completion state may have N true only if M is true. Which clause forbids exactly the violating state?

    • not-N or M
    • not-M or N
    • M or N

  8. Ned claims that adding clause learning proves a SAT solver has polynomial worst-case runtime. Which response is justified?

    • Learning guarantees a polynomial bound for every formula
    • Learning alone gives no such bound
    • Learning changes SAT into a different decision problem
LightMySky · lightmysky.comW1-mt_d46m2LD443-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Search that learns from failure W1-mt_d46m2LD443-s1

  1. Learned clauses implied by the original formula · Conflict analysis derives implied clauses. Retained learned clauses constrain later search without removing satisfying assignments.
  2. Every encoded rule holds · Satisfaction makes every clause true. In a correct encoding, every encoded rule is therefore obeyed.
  3. False · SAT's NP-completeness permits easy inputs and useful solvers. Selected runtimes do not establish a polynomial algorithm for all SAT inputs.
  4. P · P false would force both Q true and Q false. Every satisfying assignment therefore has P true, so the unit clause P is implied.
  5. not-A or not-B · The forbidden assignment is A true and B true. Not-A or not-B is false exactly on that assignment.
  6. No; one false clause is enough · The conjunction requires every clause to be true. One false clause makes the formula false under this assignment.
  7. not-N or M · The violating state has N true and M false. Not-N or M is false exactly there, encoding N implies M.
  8. Learning alone gives no such bound · Pruning some searches does not prove a polynomial bound on every run. No general polynomial-time SAT algorithm is known.
Worksheet · LightMySky