The bijunctive algorithm seed measure is a probability measure
ProvedStabilityDichotomies.Bijunctive.bijunctive_seed_is_probabilityconstraint-satisfactionprobability
For ε > 0 and a fixed two-CNF representation with positive clause bound, the seed measure of Definition 4.8 is a probability measure. It is the finite independent product of uniform occurrence priorities, a uniform cutoff on [1−ε/2,1], and exponential literal shifts at the positive rate ε/(2bΓ). This verifies normalization of the random input; output-event measurability and algorithmic guarantees are separate.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_BijunctiveLaw noncomputable section open scoped Classical ENNReal open MeasureTheory ProbabilityTheory StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.bijunctive_seed_is_probability {Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (I : Instance Γ V) (ε : ℝ) (hε : 0 < ε) :
IsProbabilityMeasure (bijunctiveSeedMeasure rep I ε) := by sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean Constraint Satisfaction Problems, STOC 2027 submission #535, Definition 4.8, p. 19, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf