Theorem 5.10 — worst-case simulation of E in low space
OpenAvoidPlast.Supplement.theorem_5_10complexity-theoryexponential-timep2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computation
Assume that for every and every there is an algorithm of space such that for all . Then
Differences from the source:
- encoding: space , → with an explicit existential constant, ; reason: the mission's reading R2; the covers
Preamble
import Mathlib import Definitions.Def_AvoidPlast_Accepts import Definitions.Def_AvoidPlast_Machine import Definitions.Def_AvoidPlast_SpaceO import Definitions.Def_AvoidPlast_prob import Definitions.Def_AvoidPlast_Supplement_InP import Definitions.Def_AvoidPlast_Supplement_InE import Definitions.Def_AvoidPlast_Supplement_InSPACE
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 5.10, worst-case simulation of E in low space (Li–Tell, *Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance*, STOC 2027 submission manuscript (sha256 e1ff3a9e…d6728), p.26). If for every `L ∈ P` and
every `ε > 0` some machine `A` of space `n^ε` has `Pr_{x∈{0,1}^n}[A(x) = L(x)] ≥ .999` for all `n`,
then `E ⊆ ∩_{ε>0} SPACE[2^{εn}]`. -/
theorem theorem_5_10
(h : ∀ L : Set (List Bool), InP L → ∀ ε : ℝ, 0 < ε → ∃ A : Machine 1,
SpaceO A (fun n => (n : ℝ) ^ ε) ∧
∀ n : ℕ, (0.999 : ℝ) ≤ prob n (fun x => Accepts A ![x] ↔ x ∈ L)) :
∀ L : Set (List Bool), InE L → ∀ ε : ℝ, 0 < ε → InSPACE (fun n => (2 : ℝ) ^ (ε * n)) L := by sorry
end AvoidPlast.Supplement
Source
Li–Tell, Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance, STOC 2027 submission (manuscript sha256 e1ff3a9e…), Theorem 5.10, p.26 (PDF p.28)