Theorem 3.14 — the average-case conclusions imply
OpenAvoidPlast.Supplement.theorem_3_14complexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computationspace-hierarchy
Assume that for some fixed , every has a machine of space such that for every there is with . Then .
The hypothesis is much weaker than the average-case simulations of Theorems 5.8 and 5.14, so those conclusions would separate from .
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_Supplement_InP import Definitions.Def_AvoidPlast_Supplement_InPSPACE
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 3.14 (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). If for some fixed `c > 0` every `L ∈ P` has a machine `M_L` of
space `n^c` that, for every `n`, agrees with `L` on at least one `x ∈ {0,1}^n`, then `P ≠ PSPACE`. -/
theorem theorem_3_14 (h : ∃ c : ℝ, 0 < c ∧ ∀ L : Set (List Bool), InP L → ∃ M : Machine 1,
SpaceO M (fun n => (n : ℝ) ^ c) ∧
∀ n : ℕ, ∃ x : List Bool, x.length = n ∧ (Accepts M ![x] ↔ x ∈ L)) :
{L : Set (List Bool) | InP L} ≠ {L | InPSPACE 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.14, p.16 (PDF p.18)