FPRD LabShare an approach

← Claims

Theorem · sharp parameterized family

CRD-SAT-11a

Clause width gives a sharp propagation depth

Exact statement

For every r≥3r\ge3, there are connected, semantically equivalent strict-rr-CNF databases DrD_r and Dr+D_r^+ whose unit-propagation signatures agree through seed size r−2r-2 and first differ at seed size r−1r-1. The added clause is a pure resolvent and a reverse-unit-propagating consequence.

StatusProved for every clause width r at least three
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

The family generalizes the four-variable example and supplies the lower bound used in the later completeness-radius theorem.

Definitions

  • Let Ar=z1∨⋯∨zr−3∨¬zr−2A_r=z_1\vee\cdots\vee z_{r-3}\vee\neg z_{r-2}, with empty positive prefix at r=3r=3.
  • Set Cr−=(Ar∨x∨¬p)C_r^-=(A_r\vee x\vee\neg p), Cr+=(Ar∨y∨p)C_r^+=(A_r\vee y\vee p), Dr=Cr−∧Cr+D_r=C_r^-\wedge C_r^+, and Dr+=Dr∧(Ar∨x∨y)D_r^+=D_r\wedge(A_r\vee x\vee y).

Hypotheses and scope

  • r≥3r\ge3; all displayed clauses have exactly rr distinct literals.
  • Signatures compare closure and conflict status on every consistent seed through the stated size.

Proof or evidence

Resolving the two parents on pp gives the addition, hence semantic equivalence. CRD-SAT-10a gives agreement through depth r−2r-2. The seed x=y=z1=⋯=zr−3=0x=y=z_1=\cdots=z_{r-3}=0 has size r−1r-1: the parents reduce to (¬zr−2∨¬p)∧(¬zr−2∨p)(\neg z_{r-2}\vee\neg p)\wedge(\neg z_{r-2}\vee p) and stall, while the resolvent propagates zr−2=0z_{r-2}=0. Negating the resolvent makes the parents propagate opposite values of pp, establishing the RUP witness.

Arbitrary-width interaction-depth proof →

Verification notes

The all-width proof, the explicit first separating seed, and the RUP claim were reconstructed from the preserved checkpoint. Widths three through twelve are finite corroboration only.

Limitations

  • The growing interaction depth is carried by growing clause width.
  • The theorem does not give unbounded depth inside strict 3CNF.

Open work

Compare the family with standard propagation-hardness and absorption examples before making a novelty claim.