FPRD LabShare an approach

← Claims

Theorem · exact decision law

CRD-SAT-11b

The retained resolvent saves one fixed-policy decision

Exact statement

Under false-first DPLL order x<y<z1<⋯<zr−2<px<y<z_1<\cdots<z_{r-2}<p, exhaustive unit propagation, and stopping when every stored clause is satisfied, DrD_r uses rr decisions and Dr+D_r^+ uses r−1r-1, with no conflicts on either successful trace.

StatusProved for the stated family and fixed DPLL interface
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

The result measures the operational effect that first appears at the sharp propagation depth.

Hypotheses and scope

  • The databases are those of CRD-SAT-11a.
  • Branching order, false-first polarity, exhaustive propagation, and the clause-satisfaction stopping rule are fixed as stated.

Proof or evidence

The base solver decides false for x,y,z1,…,zr−3x,y,z_1,\ldots,z_{r-3} and must also decide zr−2=0z_{r-2}=0, totaling rr. In the augmented database, the retained resolvent becomes unit after the first r−1r-1 decisions and propagates that last value. Both traces then satisfy every stored clause without conflict.

Exact decision calculation →

Verification notes

The exact traces were reconstructed symbolically; the checker through width twelve is corroboration.

Limitations

  • Choosing zr−2z_{r-2} earlier can erase the saving.
  • The theorem does not establish a conflict, proof-size, or average-runtime separation.

Open work

Keep the fixed order, polarity, and syntactic stopping rule attached to the resource claim.