Semantic existential consequence of the Horn/dual-Horn upper bound
ProvedStabilityDichotomies.Solvability.horn_dual_horn_approximation_upperFor every finite Horn or dual-Horn Boolean constraint language , there is a constant such that, for every , some solver -approximates every satisfiable instance and has average sensitivity at most on every satisfiable instance. Horn and dual-Horn are expressed by closure under coordinatewise AND and OR. Scope: this is a semantic existential consequence of Theorem 4.3. The unrestricted Solver type does not encode its particular thinning algorithm or any runtime guarantee; the full algorithm-specific theorem remains to be formalized.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Core noncomputable section open scoped Classical
Formal statement
namespace StabilityDichotomies.Solvability
theorem horn_dual_horn_approximation_upper (Γ : Language)
(hΓ : (∀ R ∈ Γ.relations, ∀ x y : Fin R.arity → Bool,
x ∈ R.tuples → y ∈ R.tuples → (fun i => x i && y i) ∈ R.tuples) ∨
(∀ R ∈ Γ.relations, ∀ x y : Fin R.arity → Bool,
x ∈ R.tuples → y ∈ R.tuples → (fun i => x i || y i) ∈ R.tuples)) :
∃ C : ℝ, 0 < C ∧ ∀ ε : ℝ, 0 < ε → ε ≤ 1 →
∃ A : Solver Γ, Approximates A ε ∧
∀ (V : Type) [Fintype V] (I : Instance Γ V), Satisfiable I →
averageSensitivity A I ≤ C * ε⁻¹ := by
sorry
end StabilityDichotomies.SolvabilitySource
Wang and Yoshida, Stability Dichotomies for Boolean Constraint Satisfaction Problems, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf, Theorem 4.3, p.16; semantic existential consequence only.