FPRD LabShare an approach

← Claims

Corollary · sharp bound

CRD-SAT-12b

The UP completeness radius w−1 is sharp

Exact statement

The exact unit-propagation completeness radius for additions of width at most ww is w−1w-1: depth w−1w-1 always suffices, while for every w≥3w\ge3 there are semantically equivalent pairs agreeing through depth w−2w-2 and separating at a seed of size w−1w-1.

StatusProved from the absorption theorem and the preserved width-w family
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

The upper bound is general; the lower bound identifies the first seed size at which a width-w retained clause can become visible to UP.

Hypotheses and scope

  • w≥3w\ge3 for the separating family.
  • Added clauses have width at most ww; allowing wider additions changes the radius.

Proof or evidence

CRD-SAT-12a gives the upper bound w−1w-1. The preserved Run 25 family has a width-ww addition that is inactive on every smaller seed and becomes unit on an explicit seed of size w−1w-1, giving the matching lower bound. Widths three through eight were rerun as finite corroboration.

Sharp completeness-radius proof →

Verification notes

The upper and lower bounds were kept logically separate. The lower-bound family is now stated and proved as CRD-SAT-11a.

Limitations

  • The width bound applies to the added clauses, not necessarily every clause in the base.
  • The result does not bound interaction depth when learned-clause width is unbounded.

Open work

Compare the exact radius with standard propagation-hardness and absorption formulations.