PropagationGraph
The structure encodes a directed graph on n variables where an edge from u to v means determining u forces v through propagation. Analysts of SAT completeness and backpropagation algorithms cite it when modeling reachability from unit constraints to full assignments. It is introduced as a structure with one field for the forcing relation, directly enabling inductive reachability predicates.
claimA propagation graph on $n$ variables consists of a binary relation on the set of variables indexed by $0$ to $n-1$ such that an edge from $u$ to $v$ holds when fixing the value of $u$ determines the value of $v$.
background
The module builds fully-determined backpropagation states from total assignments to SAT instances. Variables are indexed by Fin n. The graph captures directed forcing dependencies between variables to support propagation from initial units.
proof idea
As a structure definition it directly specifies the type with its single edges field. No lemmas or tactics are applied.
why it matters in Recognition Science
It supplies the graph type required by AllReachable and IsolationInvariant. The latter asserts connectivity from units under the isolation construction in Track A, supporting the polynomial-time 3SAT algorithm hypothesis by ensuring propagation reaches all variables without stalls.
scope and limits
- Does not construct the edges from a CNF formula or XOR system.
- Does not incorporate an initial set of units or the reachability predicate.
- Does not enforce acyclicity or other structural properties on the graph.
- Does not address computational cost or termination of propagation.
formal statement (Lean)
58structure PropagationGraph (n : Nat) where
59 edges : Var n → Var n → Prop
60
61/-- A variable is reachable from initial units in the propagation graph.
62 Defined inductively to ensure termination. -/