Theorem 5.8 (= Theorem 1.2, general ) — low-space simulation of P on average
OpenAvoidPlast.Supplement.theorem_5_8average-case-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computation
Suppose Assumption 1.1 holds with and . Then for every , every and every there is a deterministic algorithm of space such that
where .
The base mission states the case inside Theorem 5.14; here is general.
Differences from the source:
- reading: Assumption 1.1 holds (with ) → Assumption 1.1 with one for every ; reason: the conclusion is stated in terms of ; has the type of Assumption 1.1
- reading: → for some with ; reason: is evaluated at the padded input length of the proof, ; is not assumed monotone
- reading: error → for every there is an algorithm with error at most ; reason: the proofs choose the polylog freely ( repetitions, p.22); "some polylog" would allow
- 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_PrBPstarLEqPrL import Definitions.Def_AvoidPlast_SpaceO import Definitions.Def_AvoidPlast_lg import Definitions.Def_AvoidPlast_prob import Definitions.Def_AvoidPlast_Supplement_InP import Definitions.Def_AvoidPlast_Supplement_Assumption11With
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 5.8 (= Theorem 1.2, one direction, general `p`) (Li–Tell, *Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance*, STOC 2027 submission manuscript (sha256 e1ff3a9e…d6728), p.25). Suppose Assumption 1.1
holds with `p : ℕ → (0,1)` and `prBP*L = prL`. Then for every `L ∈ P`, every `ε > 0` and every
polylog exponent `e ≥ 1` there is a deterministic machine `A` of space `O(n^ε)` with
`Pr_{x∈{0,1}^n}[A(x) = L(x)] ≥ 1 - 3(p(N(n)) + 2^{-(lg n)^e})` for all `n`, where
`n ≤ N(n) ≤ b n^b + b` (the `p(n^{O(1)})` of the source). -/
theorem theorem_5_8 (p : ℕ → ℝ) (hp : ∀ n, 0 < p n ∧ p n < 1) (hA : Assumption11With p)
(hD : PrBPstarLEqPrL) :
∀ L : Set (List Bool), InP L → ∀ ε : ℝ, 0 < ε → ∀ e : ℝ, 1 ≤ e →
∃ (A : Machine 1) (N : ℕ → ℕ) (b : ℕ), SpaceO A (fun n => (n : ℝ) ^ ε) ∧
(∀ n : ℕ, n ≤ N n ∧ N n ≤ b * n ^ b + b) ∧
∀ n : ℕ, 1 - 3 * (p (N n) + (2 : ℝ) ^ (-(lg n) ^ e)) ≤
prob n (fun x => Accepts A ![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 5.8, p.25 (PDF p.27)