Existence of the exact thinning output law
ProvedStabilityDichotomies.Solvability.thinning_output_law_existsconstraint-satisfactionprobability
For any Boolean constraint language Γ and either extremal selection b, and every 0 < ε ≤ 1, there exists a semantic solver whose distribution on satisfiable inputs is exactly the uniform mixture of independent constraint-retention laws in Definition 4.2. This statement constructs the probability law as a normalized finite distribution; it makes no claim about executable runtime or sensitivity.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Thinning noncomputable section open scoped Classical BigOperators Interval open MeasureTheory StabilityDichotomies.Solvability
Formal statement
theorem StabilityDichotomies.Solvability.thinning_output_law_exists (Γ : Language) (b : Bool) (ε : ℝ)
(hε : 0 < ε) (hε1 : ε ≤ 1) : ∃ A : Solver Γ, ThinningOutputLaw Γ b ε A := by sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean Constraint Satisfaction Problems, STOC 2027 submission #535, Definition 4.2, p. 16, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf