`sat_recognition_time`

proved

show as: view math explainer →

module: IndisputableMonolith.Complexity.CellularAutomata
domain: Complexity
line: 245 · 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 245.

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

depends on

formal source

 242one pair of tapes that match on the observed bits but differ in the total parity (and thus
 243the result). -/
 244/-!
 245theorem sat_recognition_time (n : ℕ) (hn : 0 < n) :
 246    ∃ (c : ℝ), c > 0 ∧
 247    ∀ (decoder : Fin n → Bool → Prop),
 248      -- Any decoder that reads fewer than n bits cannot determine SAT result
 249      (∃ M : Finset (Fin n), M.card < n ∧
 250        ∀ result : Bool, ∃ tape1 tape2 : Fin n → Bool,
 251          (∀ i ∈ M, tape1 i = tape2 i) ∧
 252          decoder tape1 result ∧ ¬decoder tape2 result)
 253-/
 254
 255/-- **THE SEPARATION**: Tc << Tr (documentation / TODO)
 256
 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.