Theorem 1.8 (= Corollary 6.7) — hardness of Avoid for tiny-error non-deterministic algorithms
OpenAvoidPlast.Supplement.theorem_1_8average-case-complexitycomplexity-theorydemi-bitsp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computation
Let be a relaxed -demi-bits generator against . For let ,
with written in bits and unused codes mapped to . Then:
- if is computable in space , the family (indexed by , of length ) is evaluable in space ;
- no non-deterministic polynomial-time machine satisfies, for every sufficiently large ,
In terms of the index length this is Theorem 1.8: a non-deterministic algorithm for that errs on at most of the inputs succeeds on less than of them.
Differences from the source:
- encoding: →
g : ℕ → List Bool → List Boolwithhg: maps every seed of length (truncated subtraction) to an -bit string, ; reason: the type of the family; values off the domain are never used; the subtraction truncates only when , where the source's type is undefined - reading: Theorem 1.8 ("there is a family ... errs on at most ... succeeds on less than ") → Corollary 6.7's explicit form for the family , with the evaluability of Theorem 1.8 as item 1; reason: "Corollary 6.7 (Theorem 1.8, restated)", p.36
- reading: → reads the index ; reason: is an indexed family (Theorem 1.8); a circuit description would contain 's circuit, which need not be efficiently constructible, and the proof runs inside an NP/AM verifier given
- reading: the demi-bits definition and "no ... with the following parameters" (stated for one ) → a verifier or algorithm must work for every sufficiently large ; reason: a uniform machine is asymptotic; Corollary 6.7 says "for every sufficiently large "
- reading: "evaluable in space " → space on indices of length ; reason: the "Observe" sentence of Corollary 6.7: evaluating costs computing plus space
- reading: "computable in space " (no definition) → a machine given in binary and the seed prints (seed) in work space ; reason: the paper gives no definition; is indexed by because the seed length does not determine
- encoding: ; in bits →
Real.logb 2,Nat.clog 2; least significant bit first; reason: a fixed binary convention
Preamble
import Mathlib import Definitions.Def_AvoidPlast_EvaluableInSpace import Definitions.Def_AvoidPlast_Machine import Definitions.Def_AvoidPlast_prob import Definitions.Def_AvoidPlast_Supplement_IsPolyNTime import Definitions.Def_AvoidPlast_Supplement_demiCs import Definitions.Def_AvoidPlast_Supplement_AvoidDemiSucc import Definitions.Def_AvoidPlast_Supplement_AvoidDemiSound import Definitions.Def_AvoidPlast_Supplement_IsRelaxedDemiBitsAM import Definitions.Def_AvoidPlast_Supplement_ComputableInSpaceIdx
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 1.8 in the form of Corollary 6.7, average-case hardness for tiny-error
non-deterministic algorithms (Li–Tell, *Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance*, STOC 2027 submission manuscript (sha256 e1ff3a9e…d6728), p.5 and pp.36–37). Let `g = {g_n}`,
`g_n : {0,1}^{n - ⌈log n⌉ - 1} → {0,1}^n`, be a relaxed `1/4`-demi-bits generator against AM, and for
`s = (s_1, …, s_n) ∈ {0,1}^{n×n}` let `C_s(x, i) = g(x) ⊕ s_i` (`i` in `⌈log n⌉` bits, unused codes
mapped to `s_1`). Then
1. if `g` is computable in space `s(n) ≥ log n`, the family `{C_s}` indexed by `s` (of length
`N = n²`) is evaluable in space `O(s(n))` (the "Observe" sentence of Corollary 6.7);
2. no non-deterministic polynomial-time machine `A` satisfies, for every sufficiently large `n`,
`Pr_s[∃ w : A(C_s, w) ∈ {0,1}^n \ Range(C_s)] ≥ 3·2^{-n}` and
`Pr_s[∀ w : A(C_s, w) ∉ Range(C_s)] ≥ 1 - 2^{-2n}`.
**Formalization Note** `A` reads the index `s`. The index has `N = n²` bits, so `2^{-2n}` and
`3·2^{-n}` are Theorem 1.8's `2^{-2√N}` and `O(2^{-√N})`; the evaluation space is stated as
`O(s(√N))`, the cost of computing `g` at output length `n`. -/
theorem theorem_1_8 (g : ℕ → List Bool → List Bool)
(hg : ∀ n x, x.length = n - (Nat.clog 2 n + 1) → (g n x).length = n)
(hdemi : IsRelaxedDemiBitsAM g (fun n => n - (Nat.clog 2 n + 1)) (fun _ => 1 / 4)) :
(∀ sp : ℕ → ℝ, (∀ n : ℕ, Real.logb 2 n ≤ sp n) →
ComputableInSpaceIdx g (fun n => n - (Nat.clog 2 n + 1)) sp →
EvaluableInSpace
(fun s z => demiCs g (fun n => Nat.clog 2 n + 1) (fun n => n) (Nat.sqrt s.length) s z)
(fun N => Nat.sqrt N - 1) (fun N => Nat.sqrt N) (fun N => sp (Nat.sqrt N))) ∧
¬ ∃ (A : Machine 2) (a : ℕ), IsPolyNTime A a ∧ ∀ᶠ n : ℕ in Filter.atTop,
3 * (2 : ℝ) ^ (-(n : ℝ)) ≤
prob (n * n) (AvoidDemiSucc A a g (fun n => Nat.clog 2 n + 1) (fun n => n) n) ∧
1 - (2 : ℝ) ^ (-(2 * n : ℝ)) ≤
prob (n * n) (AvoidDemiSound A a g (fun n => Nat.clog 2 n + 1) (fun n => n) n) := 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 1.8, p.5 (PDF p.7), and Corollary 6.7, pp.36–37 (PDF pp.38–39)