CARuntimeModel

formal source

  10  steps  : Nat
  11
  12/-- Abstract packaging of the CA runtime bound assumptions. -/
  13structure CARuntimeModel where
  14  /-- Grid side length as a function of number of inputs n. -/
  15  sideLength : ℕ → ℕ
  16  /-- Assumption: side length is Θ(n^{1/3}). -/
  17  sideLength_bound : ∃ c₁ c₂ : ℝ, 0 < c₁ ∧ 0 < c₂ ∧
  18    ∀ n : ℕ, c₁ * (n : ℝ)^(1/3 : ℝ) ≤ (sideLength n : ℝ) ∧
  19         (sideLength n : ℝ) ≤ c₂ * (n : ℝ)^(1/3 : ℝ)
  20  /-- Locality: constraints are realized by gadgets of O(1) diameter (abstract). -/
  21  locality : Prop
  22
  23/-- Logical propagation depth (number of implication layers). -/
  24noncomputable def logicalDepth (n : ℕ) : ℕ := Nat.ceil (Real.logb 2 (n + 1))
  25
  26/-- CA time bound target: O(n^{1/3} * log n) under locality and O(log n) logical depth. -/
  27def caTimeBound (M : CARuntimeModel) (n : ℕ) : Prop :=
  28  ∃ c : ℝ, 0 < c ∧ (M.sideLength n : ℝ) * (logicalDepth n : ℝ) ≤ c * (n : ℝ)^(1/3 : ℝ) * Real.log (n + 2)
  29
  30/-- CA→TM simulation cost: TM time = O(volume * steps).
  31    The actual content would specify that a Turing Machine can simulate
  32    a cellular automaton with volume V and time T in O(V·T) steps. -/
  33def ca_to_tm_simulation_prop {n} (rt : CARuntime n) : Prop :=
  34  ∃ c : Nat, c > 0 ∧ rt.volume * rt.steps ≤ c * n^2 -- Simplified polynomial bound
  35
  36/-- Target bound for the full 3-SAT algorithm.
  37    Total TM time is bounded by O(n^{11/3} log n). -/
  38def three_sat_runtime_prop (n : Nat) : Prop :=
  39  ∃ c : ℝ, c > 0 ∧ (n : ℝ)^(11/3 : ℝ) * Real.log (n + 2) ≤ c * (n : ℝ)^4
  40
  41
  42end SAT
  43end Complexity