Theorem 5.9 (= Theorem 1.3) — linear-time simulation of P on average
OpenAvoidPlast.Supplement.theorem_5_9alternationaverage-case-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computation
Suppose Assumption 1.1 holds with for families evaluable in simultaneous time and space , and for some . Then every has a constant such that for every some linear-time machine decides correctly on at least a
fraction of the -bit inputs, for every , where .
Time is traded for alternations: polynomial time becomes linear time with a constant number of alternations, on average.
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: "decides correctly on at least ... of the -bit inputs" → for every ; reason: the source gives no quantifier; a linear-time machine can be corrected on finitely many lengths, so this is the stronger form
- reading: → is chosen before ; reason: "" depends on only; the polylog factor in the verifier's time does not change
- encoding: SAT-oracle circuits → AND/OR/NOT gates and SAT gates of any fan-in under a fixed CNF encoding; size is the number of gates; reason: the paper fixes no encoding; any two polynomial-time encodings change sizes polynomially, absorbed by
Preamble
import Mathlib import Definitions.Def_AvoidPlast_Machine import Definitions.Def_AvoidPlast_lg import Definitions.Def_AvoidPlast_prob import Definitions.Def_AvoidPlast_Supplement_InP import Definitions.Def_AvoidPlast_Supplement_IsSigmaMachine import Definitions.Def_AvoidPlast_Supplement_sigmaAccepts import Definitions.Def_AvoidPlast_Supplement_SATLowerBound import Definitions.Def_AvoidPlast_Supplement_Assumption11TSWith
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 5.9 (= Theorem 1.3) (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)`
for families evaluable in simultaneous time `poly(n)` and space `n^{ε²}`, and
`DSPACE[O(n)] ⊄ i.o.SIZE^SAT[2^{δn}]` for some `δ > 0`. Then every `L ∈ P` has a constant `k = k_L`
such that, for every polylog exponent `e ≥ 1`, a linear-time `Σ_k` machine decides `L` correctly
on at least a `1 - 3(p(N(n)) + 2^{-(lg n)^e})` fraction of the `n`-bit inputs, for every `n`,
where `n ≤ N(n) ≤ b n^b + b`. -/
theorem theorem_5_9 (p : ℕ → ℝ) (hp : ∀ n, 0 < p n ∧ p n < 1) (hA : Assumption11TSWith p)
(hS : SATLowerBound) :
∀ L : Set (List Bool), InP L → ∃ k : ℕ, ∀ e : ℝ, 1 ≤ e →
∃ (V : Machine (k + 1)) (C : ℕ) (N : ℕ → ℕ) (b : ℕ), IsSigmaMachine k V (fun n => n) C ∧
(∀ n : ℕ, n ≤ N n ∧ N n ≤ b * n ^ b + b) ∧
∀ n : ℕ, 1 - 3 * (p (N n) + (2 : ℝ) ^ (-(lg n) ^ e)) ≤
prob n (fun x => sigmaAccepts k V (fun n => n) C 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.9, p.25 (PDF p.27)