Fixed-initialization MT and structural formula predicates
DefinitionMTWalkSAT3CNF_TwoOcc_Supplement_RuntimeFor an indexed 3-CNF formula , a legal history-adaptive rule and a fixed assignment , the MT trajectory starts at the Dirac law of and uses the published MT transition kernel unchanged. Its mean is
The additional structural predicates mean that admits a satisfying assignment, that different clause indices have different sets of signed literals, that the largest occurrence count is exactly three, and that a variable has a specified number of positive or negative occurrences. The triple constructor checks only distinctness of its three variables. Finite clause families are reindexed by a bijection with , preserving all duplicate indices. These interfaces supply the fixed-initialization bounds and structural conclusions of §4 without assuming them.
import Definitions.Def_MTWalkSAT3CNF_TwoOcc_MoserTardos
import Definitions.Def_MTWalkSAT3CNF_TwoOcc_WalkSAT
set_option autoImplicit false
namespace MTWalkSAT3CNF.TwoOcc.Supplement
open MeasureTheory ProbabilityTheory
open scoped ENNReal
variable {V : Type} [Fintype V] [DecidableEq V] {m : ℕ}
/-- Fixed-initial-assignment MT law; the published transition kernel is unchanged. -/
noncomputable def mtLawFrom (F : Formula V m) (R : MTRule (cnfSystem F))
(σ : V → Bool) : Measure (ℕ → MTState (fun _ : V => Bool) (Fin m)) :=
Kernel.trajMeasure (Measure.dirac (σ, Choice.none)) ((cnfSystem F).mtStep R)
noncomputable def mtMeanFrom (F : Formula V m) (R : MTRule (cnfSystem F))
(σ : V → Bool) : ℝ≥0∞ :=
∫⁻ ω, ((cnfSystem F).mtTimeOf ω : ℝ≥0∞) ∂mtLawFrom F R σ
/-- Satisfaction of all indexed clauses. -/
def Satisfiable (F : Formula V m) : Prop := ∃ σ, bad F σ = ∅
/-- Clause equality ignores permutation of literal positions; indices are retained. -/
def NoRepeated (F : Formula V m) : Prop :=
Function.Injective (fun i => Finset.univ.image (fun p => ((F i).var p, (F i).sign p)))
def MaxOccThree (F : Formula V m) : Prop :=
(∀ v, occCount F v ≤ 3) ∧ ∃ v, occCount F v = 3
def signedOcc (F : Formula V m) (v : V) (s : Bool) : ℕ :=
(Finset.univ.filter (fun ip : Fin m × Fin 3 =>
(F ip.1).var ip.2 = v ∧ (F ip.1).sign ip.2 = s)).card
/-- A structural constructor only: its proof establishes that the three positions are distinct. -/
def triple (a b c : V) (s t u : Bool) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) :
Clause V where
var := ![a,b,c]
sign := ![s,t,u]
var_inj := by
intro i j hij
fin_cases i <;> fin_cases j <;> simp_all
/-- Reindex a finite clause family without identifying repeated clauses. -/
noncomputable def indexed {I : Type} [Fintype I] (C : I → Clause V) :
Formula V (Fintype.card I) := fun i => C ((Fintype.equivFin I).symm i)
end MTWalkSAT3CNF.TwoOcc.Supplement