FPRD LabShare an approach

← Claims

Theorem · exact equivalence

CRD-SAT-12a

Absorption characterizes bounded-width UP equivalence

Exact statement

Let G=F∪AG=F\cup A, where every added clause has width at most ww. Equality of the complete unit-propagation signatures through seed size w−1w-1, UP-absorption of every clause in AA by FF, and equality of UP closure and conflict outcomes on every consistent seed are equivalent.

StatusProved for arbitrary CNF bases and finite bounded-width additions
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

The theorem asks how deeply unit propagation must be tested before bounded-width retained clauses are known to preserve every UP consequence.

Definitions

  • For ℓ∈C\ell\in C, the boundary seed B(C,ℓ)B(C,\ell) falsifies every literal of CC except ℓ\ell.
  • Clause CC is UP-absorbed by FF when unit propagation from every B(C,ℓ)B(C,\ell) either conflicts or derives ℓ\ell.

Hypotheses and scope

  • Clauses are normalized non-tautological sets of literals.
  • The set AA is finite and every added clause has width at most ww.
  • UP closure retains conflict as a distinct outcome.

Proof or evidence

Signature equality through depth w−1w-1 handles every boundary seed and therefore implies absorption. A propagation-persistence lemma shows that consequences from a boundary seed survive every consistent extension unless a conflict appears. Hence an absorbed addition can never supply the first new unit or conflict beyond the base closure. This proves all-seed equality; restriction gives the reverse implication. The packet reports 110,397 finite configurations as corroboration.

Fixed-width absorption theorem →

Verification notes

The three implications and the propagation-persistence induction were reconstructed from the checkpoint. The proof applies to arbitrary bases and does not rely on the finite checker.

Limitations

  • The theorem concerns exhaustive unit-propagation closure and conflict outcomes.
  • Syntax-sensitive heuristics, clause activity, watches, reasons, acquisition, deletion, and proof cost remain outside the observer.
  • No novelty or external-review claim is made.

Open work

Compare the definition and equivalence with standard SAT absorption terminology before making a novelty claim.