Theorem 3.13 — space hierarchy on all inputs
OpenAvoidPlast.Supplement.theorem_3_13complexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computationspace-hierarchy
For all reals there is a language that is hard for infinitely often on all inputs: for every machine of space there are infinitely many such that
It is the hierarchy theorem behind Theorem 3.14, which turns the paper's average-case conclusions into .
Differences from the source:
- reading: "for every " → ; reason: "-space machine" with , as in Theorem 3.14 where it is applied
- 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_Supplement_InSPACE
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 3.13, a space hierarchy on all inputs (Li–Tell, *Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance*, STOC 2027 submission manuscript (sha256 e1ff3a9e…d6728), p.16). For all reals `0 < c < C` there
is `L ∈ SPACE[n^C]` such that for every machine `M` of space `n^c` there are infinitely many `n`
with `M(x) ≠ L(x)` for **every** `x ∈ {0,1}^n`.
**Formalization Note** Space `n^c` is `O(n^c)` with halting on every input (`SpaceO`, reading R2);
`M(x) ≠ L(x)` is that acceptance of `x` differs from membership. -/
theorem theorem_3_13 : ∀ c C : ℝ, 0 < c → c < C → ∃ L : Set (List Bool),
InSPACE (fun n => (n : ℝ) ^ C) L ∧ ∀ M : Machine 1, SpaceO M (fun n => (n : ℝ) ^ c) →
∃ᶠ n : ℕ in Filter.atTop, ∀ x : List Bool, x.length = n →
¬ (Accepts M ![x] ↔ x ∈ 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 3.13, p.16 (PDF p.18)