Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.4 — simulating NP by a low-space AM verifier from hardness of Avoid

Open
AvoidPlast.Supplement.theorem_5_4

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

average-case-complexitycomplexity-theoryinteractive-proofsp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computation

There are a universal c>1c>1c>1 and ε0>0\varepsilon_0>0ε0​>0 such that the following holds. Let δ>0\delta>0δ>0, let X,YX,YX,Y be ensembles with YYY samplable in polynomial time and space nδn^\deltanδ, and let TTT be a nice increasing function with T(n)≥nT(n)\ge nT(n)≥n. Let δ<ε<ε0\delta<\varepsilon<\varepsilon_0δ<ε<ε0​, mmm with ncε≤m(n)≤nn^{c\varepsilon}\le m(n)\le nncε≤m(n)≤n, and C[nδ→m(n)]C[n^\delta\to m(n)]C[nδ→m(n)] an indexed family such that AvoidC\mathrm{Avoid}_CAvoidC​ cannot be solved by any SearchNTimeGuess[poly(n),nε]\mathrm{SearchNTimeGuess}[\mathrm{poly}(n),n^\varepsilon]SearchNTimeGuess[poly(n),nε] algorithm with success p(n)p(n)p(n) or more over XYT1/εXY^{T^{1/\varepsilon}}XYT1/ε. Then for every L∈NTIME[T]L\in\mathrm{NTIME}[T]L∈NTIME[T] and every e≥1e\ge1e≥1 there is an AM verifier VLV_LVL​ with:

  1. time TO(1/ε)T^{O(1/\varepsilon)}TO(1/ε) and space O(Tδ/ε)O(T^{\delta/\varepsilon})O(Tδ/ε), not counting its randomness, which is stored on a read-only two-way tape; oracle queries to CxyC_{xy}Cxy​ with y∼YT(n)1/εy\sim Y_{T(n)^{1/\varepsilon}}y∼YT(n)1/ε​;
  2. one round (two messages), the honest prover's message having Tδ/εT^{\delta/\varepsilon}Tδ/ε bits;
  3. with probability at least 1−p(N)1-p(N)1−p(N) over x∼Xnx\sim X_nx∼Xn​ and the coins, N=n+T(n)1/εN=n+T(n)^{1/\varepsilon}N=n+T(n)1/ε, if x∈Lx\in Lx∈L then some prover message makes VLV_LVL​ accept;
  4. every x∉Lx\notin Lx∈/L is rejected, against every prover, with probability at least 1−2−(lg⁡N)e1-2^{-(\lg N)^e}1−2−(lgN)e.

Moreover, under hardness for deterministic polynomial time over XYT1/εXY^{T^{1/\varepsilon}}XYT1/ε the same holds for every L∈DTIME[T]L\in\mathrm{DTIME}[T]L∈DTIME[T].

Differences from the source:

  • reading: "Let c>1c>1c>1 be the universal constant from Theorem 5.1" → ∃c>1\exists c>1∃c>1 in this statement; reason: a statement cannot name another theorem's witness; the proof uses only ccc's role in Theorem 5.1
  • reading: "for a sufficiently small ε>δ\varepsilon>\deltaε>δ" → ∃ε0>0\exists\varepsilon_0>0∃ε0​>0 before δ\deltaδ, then δ<ε<ε0\delta<\varepsilon<\varepsilon_0δ<ε<ε0​; reason: as in Theorem 5.1
  • reading: "AvoidC\mathrm{Avoid}_CAvoidC​ cannot be solved ... with success ppp or more" → for every algorithm of the class and every sufficiently large nnn, the success probability is below p(n)p(n)p(n); reason: the proof uses the hardness at every large length (Fact 5.1.1, p.21)
  • reading: error 2−polylog(n)2^{-\mathrm{polylog}(n)}2−polylog(n) → for every e≥1e\ge1e≥1 there is an algorithm with error at most 2−(lg⁡n)e2^{-(\lg n)^e}2−(lgn)e; reason: the proofs choose the polylog freely (k=polylog(n)k=\mathrm{polylog}(n)k=polylog(n) repetitions, p.22); "some polylog" would allow 2−12^{-1}2−1
  • encoding: oracle queries to CxC_xCx​, answers scanned read-once (footnotes 21, 22) → a read-only random-access tape holding CxC_xCx​ at addresses ⟨a,i⟩\langle a,i\rangle⟨a,i⟩ (oracleTable), addresses written on work space; reason: the two models simulate each other with polynomial time overhead and O(log⁡n)O(\log n)O(logn) extra space
  • reading: the verifier draws y∼YT(n)1/εy\sim Y_{T(n)^{1/\varepsilon}}y∼YT(n)1/ε​ with its own coins → yyy is given to the verifier as part of its persistent randomness; reason: the sampler of YYY runs in time poly(T1/ε)\mathrm{poly}(T^{1/\varepsilon})poly(T1/ε) and space O(Tδ/ε)O(T^{\delta/\varepsilon})O(Tδ/ε), within the stated bounds, so such a verifier is a verifier of the source's form
  • encoding: time TO(1/ε)T^{O(1/\varepsilon)}TO(1/ε); T(n)1/εT(n)^{1/\varepsilon}T(n)1/ε; message of Tδ/εT^{\delta/\varepsilon}Tδ/ε bits → ⌈a(T(n)a/ε+1)⌉\lceil a(T(n)^{a/\varepsilon}+1)\rceil⌈a(T(n)a/ε+1)⌉ with aaa after LLL (also the length of the coins); ⌈T(n)1/ε⌉\lceil T(n)^{1/\varepsilon}\rceil⌈T(n)1/ε⌉; exactly ⌈T(n)δ/ε⌉\lceil T(n)^{\delta/\varepsilon}\rceil⌈T(n)δ/ε⌉ bits; reason: readings R2, R3; a fixed coin length carries no advice
  • encoding: Definition 5.3 when no nnn has N≥n+T0(n)N\ge n+T_0(n)N≥n+T0​(n) → n=0n=0n=0; reason: undefined in the source; only N<T0(0)N<T_0(0)N<T0​(0), finitely many lengths, which asymptotic hardness ignores
  • encoding: "YYY samplable in polynomial time and space nδn^\deltanδ" → a sampler with coins of fixed length a(Na+1)a(N^a+1)a(Na+1), time a(Na+1)a(N^a+1)a(Na+1), work space a(Nδ+1)a(N^\delta+1)a(Nδ+1), exact output law YNY_NYN​; reason: Definition 3.4 with the space bound
  • reading: "TTT a nice increasing function" → IsNice T, Monotone T (non-decreasing), n≤T(n)n\le T(n)n≤T(n); reason: "increasing" is ambiguous; non-decreasing is the weaker hypothesis, so the stronger theorem; the padding step needs only that n+⌈T(n)1/ε⌉n+\lceil T(n)^{1/\varepsilon}\rceiln+⌈T(n)1/ε⌉ increase strictly, which holds for every non-decreasing TTT
Preamble
import Mathlib
import Definitions.Def_AvoidPlast_IsNTimeVerifier
import Definitions.Def_AvoidPlast_IsNice
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_paddedDist
import Definitions.Def_AvoidPlast_Supplement_IsSampler
import Definitions.Def_AvoidPlast_Supplement_AvoidHardSNTG
import Definitions.Def_AvoidPlast_Supplement_AvoidHardDet
import Definitions.Def_AvoidPlast_Supplement_padExp
import Definitions.Def_AvoidPlast_Supplement_AMVerifier54
Formal statement
namespace AvoidPlast.Supplement

open AvoidPlast

/-- Theorem 5.4, simulating NP by a low-space AM verifier 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.23).
There are a universal `c > 1` and `ε₀ > 0` such that the following holds. Let `δ > 0`, let `X`, `Y`
be ensembles with `Y` samplable in polynomial time and space `n^δ`, and let `T` be nice,
increasing (non-decreasing, `Monotone`), with `T(n) ≥ n`. For `δ < ε < ε₀`, `m` with `n^{cε} ≤ m(n) ≤ n` and an indexed family
`C[n^δ → m(n)]`: if `Avoid_C` cannot be solved by any `SearchNTimeGuess[poly(n), n^ε]` algorithm
with success `p(n)` or more over `XY^{T^{1/ε}}`, then every `L ∈ NTIME[T]` has, for every `e ≥ 1`,
an AM verifier with items 1–4 of `AMVerifier54`. Moreover, under hardness for deterministic
polynomial time over `XY^{T^{1/ε}}`, the same holds for every `L ∈ DTIME[T]`.

**Formalization Note** The constant `c` is existential here (the source points to Theorem 5.1's).
`T(n)^{1/ε}` is `⌈T(n)^{1/ε}⌉`; `2^{-polylog(N)}` reads as in Theorem 5.1. "Increasing" is read as
non-decreasing, the weaker hypothesis: `n + ⌈T(n)^{1/ε}⌉` is strictly increasing either way, which
is all the padding step uses. -/
theorem theorem_5_4 : ∃ c : ℝ, 1 < c ∧ ∃ ε₀ : ℝ, 0 < ε₀ ∧
    ∀ δ : ℝ, 0 < δ → ∀ X Y : Ensemble, (∃ (S : Machine 2) (aS : ℕ), IsSampler S aS Y δ) →
    ∀ T : ℕ → ℕ, IsNice T → Monotone T → (∀ n, n ≤ T n) →
    ∀ (p : ℕ → ℝ) (ε : ℝ), δ < ε → ε < ε₀ →
    ∀ 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 (paddedDist X Y (padExp T ε)) C (ceilPow δ) m (ceilPow ε) p →
      ∀ (L : Set (List Bool)) (V₀ : Machine 2) (C₀ : ℕ), IsNTimeVerifier V₀ L T C₀ →
        ∀ e : ℝ, 1 ≤ e → AMVerifier54 C m δ ε T X Y p L e) ∧
    (AvoidHardDet (paddedDist X Y (padExp T ε)) C (ceilPow δ) m p →
      ∀ L : Set (List Bool), InDTIME T L → ∀ e : ℝ, 1 ≤ e →
        AMVerifier54 C m δ ε T X Y 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.4, p.23 (PDF p.25)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me