Complete forcing trees preserve satisfiability under bottom-up flips
ProvedKSATSingleFlip.Connect.forcing_tree_bottom_up_satisfiesLet be a finite Boolean CNF formula, a satisfying assignment, and a complete forcing tree under . Suppose the factor graph induced by the tree variables and all clause vertices is acyclic. Flip each tree variable exactly once in any order of nonincreasing tree depth. Then every intermediate assignment satisfies . This is the clause-preservation assertion at the heart of Observation 3.2; together with the elementary properties of flip sequences it yields the satisfying path asserted there.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_FactorGraph open scoped Classical BigOperators
Formal statement
namespace KSATSingleFlip.Connect
/-- The clause-preservation core of Observation 3.2. -/
theorem forcing_tree_bottom_up_satisfies {n : ℕ} (Φ : GFormula (Fin n)) (σ : Fin n → Bool)
(T : ForcingTree Φ σ) (hσ : σ ∈ sols Φ) (hT : T.CompleteIn Finset.univ)
(hacyclic : ((factorGraph Φ).induce {v | match v with
| Sum.inl u => u ∈ T.vars
| Sum.inr _ => True}).IsAcyclic)
(order : List (Fin n)) (hn : order.Nodup) (hv : order.toFinset = T.vars)
(ho : order.Pairwise (fun u v => T.depth v ≤ T.depth u)) :
∀ z ∈ order.scanl (fun z u => flip z u) σ, FSat z Φ := by
sorry
end KSATSingleFlip.Connect
Source
Wang, Yin, Yu, Zhang, Single-Variable Connectivity in Random k-SAT, Observation 3.2, printed p. 14 (PDF p. 16) of STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf