def
definition
caTimeBound
show as:
view math explainer →
open explainer
Generate a durable explainer page for this declaration.
open lean source
IndisputableMonolith.Complexity.SAT.Runtime on GitHub at line 27.
browse module
All declarations in this module, on Recognition.
explainer page
depends on
formal source
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
44end IndisputableMonolith