Theorem 5.6 (= Theorem 2.1) — low-space AM verifiers for P
OpenAvoidPlast.Supplement.theorem_5_6average-case-complexitycomplexity-theoryinteractive-proofsp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computation
Suppose Assumption 1.1 holds with for families evaluable in simultaneous time and space . Then for every , every and every there is an AM verifier with:
- complexity: runs in time , uses space , has prover messages of bits and bits of persistent randomness (read-only, two-way);
- average-case completeness: with probability at least over and the coins, if then some prover message makes accept;
- worst-case soundness: for every , the probability over the coins that some prover message makes accept is at most ,
where .
This is the "master result" of the paper: Theorems 5.8 and 5.9 derandomize this verifier.
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
- reading: "uses at most space" → space ; reason: reading R2; a literal fails at
- encoding: message length ; persistent random bits → exactly bits; coins of the fixed length ; reason: reading R3; a fixed coin length carries no advice
Preamble
import Mathlib import Definitions.Def_AvoidPlast_Accepts import Definitions.Def_AvoidPlast_HaltsWithin import Definitions.Def_AvoidPlast_Machine import Definitions.Def_AvoidPlast_ceilPow import Definitions.Def_AvoidPlast_lg import Definitions.Def_AvoidPlast_prob import Definitions.Def_AvoidPlast_workSpace import Definitions.Def_AvoidPlast_Supplement_InP import Definitions.Def_AvoidPlast_Supplement_Assumption11TSWith
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 5.6 (= Theorem 2.1) (Li–Tell, *Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance*, STOC 2027 submission manuscript (sha256 e1ff3a9e…d6728), p.24). Suppose Assumption 1.1 holds with `p` for families
evaluable in simultaneous time `poly(n)` and space `n^{ε²}`. Then for every `L ∈ P`, every `γ > 0`
and every polylog exponent `e ≥ 1` there is an AM verifier `V(x, ρ, z)` that runs in time
`poly(n)` and space `O(n^γ)`, has prover messages of `⌈n^γ⌉` bits and `poly(n)` bits of persistent
randomness `ρ` (a read-only tape, not counted as space), and satisfies
* average-case completeness: with probability at least `1 - p(N(n)) - 2^{-(lg n)^e}` over
`x ∈ {0,1}^n` and `ρ`, if `x ∈ L` then some message makes `V` accept;
* worst-case soundness: for every `x ∉ L`, `Pr_ρ[∃ z : V(x, ρ, z) accepts] ≤ 2^{-(lg n)^e}`,
where `n ≤ N(n) ≤ b n^b + b` (the `p(n^{O(1)})` of the source).
**Formalization Note** "Uses at most `n^γ` space" is `O(n^γ)` (reading R2). -/
theorem theorem_5_6 (p : ℕ → ℝ) (hp : ∀ n, 0 < p n ∧ p n < 1) (hA : Assumption11TSWith p) :
∀ L : Set (List Bool), InP L → ∀ γ : ℝ, 0 < γ → ∀ e : ℝ, 1 ≤ e →
∃ (V : Machine 3) (a : ℕ) (K : ℝ) (N : ℕ → ℕ) (b : ℕ),
(∀ x ρ z : List Bool, ρ.length = a * (x.length ^ a + 1) → z.length = ceilPow γ x.length →
HaltsWithin V ![x, ρ, z] (a * (x.length ^ a + 1)) ∧
(workSpace V ![x, ρ, z] : ℝ) ≤ K * ((x.length : ℝ) ^ γ + 1)) ∧
(∀ n : ℕ, n ≤ N n ∧ N n ≤ b * n ^ b + b) ∧
(∀ n : ℕ, 1 - p (N n) - (2 : ℝ) ^ (-(lg n) ^ e) ≤
prob (n + a * (n ^ a + 1)) fun xρ => xρ.take n ∈ L →
∃ z : List Bool, z.length = ceilPow γ n ∧ Accepts V ![xρ.take n, xρ.drop n, z]) ∧
∀ x : List Bool, x ∉ L →
prob (a * (x.length ^ a + 1)) (fun ρ =>
∃ z : List Bool, z.length = ceilPow γ x.length ∧ Accepts V ![x, ρ, z])
≤ (2 : ℝ) ^ (-(lg x.length) ^ e) := 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.6, p.24 (PDF p.26)