A winning root that remains feasible preserves the output bit
ProvedStabilityDichotomies.Bijunctive.score_assignment_stable_if_winning_root_remains_feasibleWith graph and shifts fixed, adding feasibility constraints does not change a variable’s output if an original maximizing root for its winning literal remains feasible. The result includes ties in the exact score-comparison rule.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Bijunctive open scoped Classical BigOperators open StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.score_assignment_stable_if_winning_root_remains_feasible {Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (G F F' : Instance Γ V) (δ : Literal V → ℝ)
(hsub : ∀ c ∈ F.constraints, c ∈ F'.constraints)
(v : V) (w : Bool) (root : Literal V) (n : ℕ)
(hw : w = decide (literalScore rep G F δ (v,false) < literalScore rep G F δ (v,true)))
(hroot : feasibleLiteral F' root)
(hmax : literalScore rep G F δ (v,w) = ((δ root - n : ℝ) : WithBot ℝ))
(hd : implicationDistance rep G root (v,w) = some n) :
decide (literalScore rep G F' δ (v,false) < literalScore rep G F' δ (v,true)) = w := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean CSPs, STOC 2027, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf, proof of Theorem 4.9, feasibility-root sensitivity step.