FPRD LabShare an approach

← Claims

Theorem · closure equivalence

CRD-SAT-13a

An absorbed clause preserves every unit-propagation closure

Exact statement

For every m≥1m\ge1, the connected strict-3CNF databases FmF_m and Gm=Fm∪{x∨y∨b}G_m=F_m\cup\{x\vee y\vee b\} are semantically equivalent and have identical unit-propagation closure and conflict outcomes on every consistent seed. The added clause is UP-absorbed and has the displayed mm-step pure-resolution derivation.

StatusProved in the stated connected strict-3CNF family
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

The family separates what unit propagation derives from which stored clauses certify those derivations.

Definitions

  • A clause is UP-absorbed by a database when every boundary assignment falsifying all but one literal either causes a conflict or unit propagation derives the remaining literal.
  • The base database FmF_m contains two guarded implication chains from a1a_1 to bb, together with C0=(x∨y∨a1)C_0=(x\vee y\vee a_1) and K=(x∨y∨¬b)K=(x\vee y\vee\neg b). The augmentation adds L=(x∨y∨b)L=(x\vee y\vee b).

Hypotheses and scope

  • m≥1m\ge1; every clause has exactly three distinct literals and the variable-clause incidence graph is connected.
  • Unit propagation is compared on every consistent partial assignment, including conflict outcomes.

Proof or evidence

The three boundary assignments for LL are handled by forward or backward propagation along the displayed chains. The earlier absorption theorem then gives equality of every UP closure. Resolving C0C_0 successively with the XiX_i chain produces LL in exactly mm displayed steps. The packet also reports 88,533 all-seed instances, 177,066 paired closures, 16,368 truth rows, and 2,080 derivation steps as finite corroboration.

Absorption and complete UP-equivalence proof →

Verification notes

The boundary cases, dependence on the earlier absorption theorem, and the distinction between an exhibited derivation and a globally shortest unrestricted resolution proof were checked against the preserved checkpoint and claim record.

Limitations

  • The displayed mm-step derivation is not claimed globally shortest.
  • Closure equality does not preserve reason selection, clause order, watch traffic, or proof work.
  • No novelty or external-review claim is made.

Open work

Compare the absorption formulation with standard SAT and proof-complexity terminology before making any novelty claim.