FPRD LabShare an approach

← Claims

Theorem · all-schedule classification

CRD-SAT-14a

The all-schedule first-UIP cost spectrum is exact

Exact statement

For every legal sequential unit-propagation schedule, reason choice, and detected conflict under x=y=0x=y=0, the first-UIP cost spectrum of FmF_m is {m+1}\{m+1\}, while the spectrum of GmG_m is {1,m+1}\{1,m+1\}. Every trace learns x∨yx\vee y.

StatusProved for the stated sequential-UP/first-UIP model
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

This removes the clause-priority dependence from the best-cost separation while showing that the shortcut is not forced to be used.

Definitions

  • A legal reason trace may choose any current unit clause, records the chosen clause as an immutable reason, and may select any currently false clause as the conflict.
  • After the decision prefix, the residual reason structure is a path v0,…,vmv_0,\ldots,v_m with opposing endpoint units; GmG_m adds the positive endpoint unit vmv_m.

Hypotheses and scope

  • Immediate conflict detection, immutable reasons, latest-trail first-UIP, and the fixed decision prefix x=0,y=0x=0,y=0.

Proof or evidence

In FmF_m, true assignments form a prefix and false assignments a suffix of the residual path. When the frontiers meet, first-UIP must eliminate all m+1m+1 path variables. In GmG_m, choosing either endpoint unit early yields a one-pivot conflict, while postponing both added endpoint opportunities reproduces the long m+1m+1-pivot path. The packet exhaustively generated 176,800 traces through m=8m=8.

All-schedule path-frontier proof →

Verification notes

The prefix-suffix frontier invariant, exhaustion of the augmented cases, and common learned clause were checked against the preserved Run 28 proof.

Limitations

  • The theorem is not about unrestricted resolution proof size.
  • Conflict scans, watched literals, restarts, deletion, and the cost of finding an optimal trace are excluded.

Open work

Use the exact spectrum when comparing best available proof work with guaranteed online work.