Theorem 5.1 — a low-space verifier for sub-linear time from hardness of Avoid
OpenAvoidPlast.Supplement.theorem_5_1average-case-complexitycomplexity-theoryinteractive-proofsp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computation
There are a universal constant and such that the following holds. Let be an ensemble of distributions, , , with , and an indexed family. Assume that cannot be solved by any algorithm with success or more over . Then for every and every there is a probabilistic verifier such that for every :
- runs in polynomial time and space and makes oracle queries to ;
- the interaction is one-way, the prover sending bits;
- with probability at least over , if then some prover makes accept with probability ;
- every is rejected, against every prover, with probability at least .
Moreover, if cannot be solved by any deterministic polynomial-time algorithm with success or more over , the same holds for every .
This is the main technical step from hardness of Avoid to space-efficient verification.
Differences from the source:
- reading: "there is a universal constant ... For any pair of sufficiently small constants " → before , , , ; reason: the threshold depends only on the PCP of Theorem 4.1 (proof, p.21)
- reading: " cannot be solved ... with success or more" → for every algorithm of the class and every sufficiently large , the success probability is below ; reason: the proof uses the hardness at every large length (Fact 5.1.1, p.21)
- 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: oracle queries to , answers scanned read-once (footnotes 21, 22) → a read-only random-access tape holding at addresses (
oracleTable), addresses written on work space; reason: the two models simulate each other with polynomial time overhead and extra space - reading: a probabilistic verifier using space → its random string has the fixed length on a read-only tape; reason: within the space bound, so two-way access adds nothing to storing it; a fixed length carries no advice; the proof uses random bits (p.22)
- encoding: the family with arbitrary → a map with for ; reason: the mission's reading R8
- encoding: "the prover sending bits"; "with probability " → a message of exactly bits; probability at least ; reason: reading R3; the usual sense of "with probability"
Preamble
import Mathlib import Definitions.Def_AvoidPlast_IsNTimeVerifier import Definitions.Def_AvoidPlast_Machine import Definitions.Def_AvoidPlast_ceilPow import Definitions.Def_AvoidPlast_Supplement_InDTIME import Definitions.Def_AvoidPlast_Supplement_Ensemble import Definitions.Def_AvoidPlast_Supplement_AvoidHardSNTG import Definitions.Def_AvoidPlast_Supplement_AvoidHardDet import Definitions.Def_AvoidPlast_Supplement_OracleVerifier51
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 5.1, a low-space verifier for sub-linear time from hardness of Avoid (Li–Tell, *Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance*, STOC 2027 submission manuscript (sha256 e1ff3a9e…d6728), p.21).
There are a universal `c > 1` and `ε₀ > 0` such that for every ensemble `D`, every `p`, all
`ε₀ > ε > δ > 0`, every `m` with `n^{cε} ≤ m(n) ≤ n` and every indexed family `C[n^δ → m(n)]`:
if `Avoid_C` cannot be solved by any `SearchNTimeGuess[poly(n), n^ε]` algorithm with success `p`
or more over `D`, then every `L ∈ NTIME[n^ε]` has, for every polylog exponent `e ≥ 1`, a verifier
with items 1–4 of `OracleVerifier51` for every `n` (polynomial time, space `O(n^δ)`, oracle
`C_x`, one prover message of `n^δ` bits, perfect completeness on a `1 - p` fraction of `D_n`,
soundness error `2^{-(lg n)^e}`). Moreover, under hardness for deterministic polynomial time the
same holds for every `L ∈ DTIME[n^ε]`.
**Formalization Note** `2^{-polylog(n)}` is "for every `e ≥ 1`, error `2^{-(lg n)^e}`" (the proof
takes `k = polylog(n)` repetitions). `s(·)` is arbitrary, so the family is a map (reading R8);
lengths `n^δ`, `n^ε` are `⌈n^δ⌉`, `⌈n^ε⌉` (reading R3). -/
theorem theorem_5_1 : ∃ c : ℝ, 1 < c ∧ ∃ ε₀ : ℝ, 0 < ε₀ ∧
∀ (D : Ensemble) (p : ℕ → ℝ) (ε δ : ℝ), 0 < δ → δ < ε → ε < ε₀ →
∀ m : ℕ → ℕ, (∀ n : ℕ, (n : ℝ) ^ (c * ε) ≤ m n ∧ m n ≤ n) →
∀ C : List Bool → List Bool → List Bool,
(∀ x y : List Bool, y.length = ceilPow δ x.length → (C x y).length = m x.length) →
(AvoidHardSNTG D.dist C (ceilPow δ) m (ceilPow ε) p →
∀ (L : Set (List Bool)) (V₀ : Machine 2) (C₀ : ℕ), IsNTimeVerifier V₀ L (ceilPow ε) C₀ →
∀ e : ℝ, 1 ≤ e → OracleVerifier51 C m δ D p L e) ∧
(AvoidHardDet D.dist C (ceilPow δ) m p →
∀ L : Set (List Bool), InDTIME (ceilPow ε) L → ∀ e : ℝ, 1 ≤ e →
OracleVerifier51 C m δ D p L 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.1, p.21 (PDF p.23)