`computation_recognition_separation`

proved

show as: view math explainer →

module: IndisputableMonolith.Complexity.CellularAutomata
domain: Complexity
line: 260 · github
papers citing: none yet

open explainer

Generate a durable explainer page for this declaration.

open lean source

IndisputableMonolith.Complexity.CellularAutomata on GitHub at line 260.

browse module

All declarations in this module, on Recognition.

explainer page

Tracked in the explainer inventory; generation is lazy so crawlers do not trigger LLM jobs.

open explainer

formal source

 257Intended claim: There is a gap between computation time (Tc) and recognition time (Tr).
 258For large n, Tc scales as O(n^{1/3} log n) while Tr scales as Ω(n). -/
 259/-!
 260theorem computation_recognition_separation (n : ℕ) (hn : 100 ≤ n) :
 261    ∃ (Tc Tr : ℝ),
 262      Tc ≤ n^(1/3 : ℝ) * Real.log n ∧
 263      Tr ≥ n ∧
 264      Tc < Tr
 265-/
 266
 267end CellularAutomata
 268end Complexity
 269end IndisputableMonolith

papers checked against this theorem

No papers in the current corpus map onto this theorem yet.