Theorem 5.4 — simulating NP by a low-space AM verifier from hardness of Avoid
OpenAvoidPlast.Supplement.theorem_5_4average-case-complexitycomplexity-theoryinteractive-proofsp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computation
There are a universal and such that the following holds. Let , let be ensembles with samplable in polynomial time and space , and let be a nice increasing function with . Let , with , and an indexed family such that cannot be solved by any algorithm with success or more over . Then for every and every there is an AM verifier with:
- time and space , not counting its randomness, which is stored on a read-only two-way tape; oracle queries to with ;
- one round (two messages), the honest prover's message having bits;
- with probability at least over and the coins, , if then some prover message makes accept;
- every is rejected, against every prover, with probability at least .
Moreover, under hardness for deterministic polynomial time over the same holds for every .
Differences from the source:
- reading: "Let be the universal constant from Theorem 5.1" → in this statement; reason: a statement cannot name another theorem's witness; the proof uses only 's role in Theorem 5.1
- reading: "for a sufficiently small " → before , then ; reason: as in Theorem 5.1
- 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: the verifier draws with its own coins → is given to the verifier as part of its persistent randomness; reason: the sampler of runs in time and space , within the stated bounds, so such a verifier is a verifier of the source's form
- encoding: time ; ; message of bits → with after (also the length of the coins); ; exactly bits; reason: readings R2, R3; a fixed coin length carries no advice
- encoding: Definition 5.3 when no has → ; reason: undefined in the source; only , finitely many lengths, which asymptotic hardness ignores
- encoding: " samplable in polynomial time and space " → a sampler with coins of fixed length , time , work space , exact output law ; reason: Definition 3.4 with the space bound
- reading: " a nice increasing function" →
IsNice T,Monotone T(non-decreasing), ; reason: "increasing" is ambiguous; non-decreasing is the weaker hypothesis, so the stronger theorem; the padding step needs only that increase strictly, which holds for every non-decreasing
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)