Reason-path compression changes fixed first-UIP work · CRD-SAT-13b

Context

The two databases have the same semantics and every UP closure, but retain different reason paths for the same conflict.

Definitions

First-UIP work is the number of resolution pivots performed until one decision-level-two literal remains.
The fixed policy scans clauses in stored order, uses the first available unit clause as an immutable reason, and restarts the scan after each propagation.

Hypotheses and scope

The databases $F_m,G_m$ and shortcut $L$ are those of CRD-SAT-13a.
In $G_m$ , $L$ has highest priority; the decision prefix is $x=0$ , then $y=0$ .

Proof or evidence

In $F_m$ , the reason chain is $C_0,X_1,\ldots,X_m$ , so resolving the conflict clause eliminates $b,a_m,\ldots,a_1$ in $m+1$ pivots. In $G_m$ , the retained clause $L$ supplies $b$ directly and resolves with the conflict clause in one pivot. The packet reports 128 deterministic traces through $m=64$ .

Fixed-policy first-UIP derivation →

Verification notes

The exact pivot count and common learned clause were reconstructed. The source explicitly makes clause priority and immutable reasons part of the measured interface.

Limitations

This is not a heuristic-independent CDCL runtime lower bound.
It does not prove a minimum unrestricted resolution length, proof-width separation, or conflict-count separation.
The acquisition cost of the shortcut is not charged.

Open work

Use CRD-SAT-14a and CRD-SAT-14b for priority-independent conclusions; retain this entry as the exact fixed-policy calculation.