Theorem 6.6 — hardness of Avoid for non-deterministic algorithms that err
OpenAvoidPlast.Supplement.theorem_6_6average-case-complexitycomplexity-theorydemi-bitsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1range-avoidancespace-bounded-computation
Let be a relaxed -demi-bits generator against , polynomially bounded, and . For let , in bits with unused codes mapped to . There is no non-deterministic polynomial-time machine (allowed to output ) that satisfies, for every sufficiently large , over uniform :
- completeness: ;
- soundness: .
Corollary 6.7 (Theorem 1.8) is the case , , .
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: → 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 "
- generalization: a relaxed -demi-bits generator, a constant (Corollary 6.7 uses ) → , any function of , no range constraint; reason: a constant is a constant function, so the statement specializes to the source's; values outside make the demi-bits hypothesis false or the completeness threshold unattainable, so no range hypothesis is needed (trap 36)
- encoding: polynomially bounded → for a constant ; reason: the usual meaning
Preamble
import Mathlib import Definitions.Def_AvoidPlast_Machine import Definitions.Def_AvoidPlast_prob import Definitions.Def_AvoidPlast_Supplement_IsPolyNTime import Definitions.Def_AvoidPlast_Supplement_AvoidDemiSucc import Definitions.Def_AvoidPlast_Supplement_AvoidDemiSound import Definitions.Def_AvoidPlast_Supplement_IsRelaxedDemiBitsAM
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 6.6, hardness of Avoid against non-deterministic algorithms that err (Li–Tell, *Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance*, STOC 2027 submission manuscript (sha256 e1ff3a9e…d6728), p.35).
Let `g_n : {0,1}^{n - λ(n)} → {0,1}^n` be a relaxed `ε`-demi-bits generator against AM, `t(n)`
polynomially bounded, `κ(n) ∈ (0,1)`, `λ(n) ≥ ⌈log t(n)⌉ + 1`, and `C_s(x, i) = g(x) ⊕ s_i` for
`s ∈ {0,1}^{t×n}` (`i` in `⌈log t⌉` bits, unused codes mapped to `s_1`). No non-deterministic
polynomial-time `A` (allowed to output `⊥`) satisfies, for every sufficiently large `n`,
`Pr_s[∃ w : A(C_s, w) ∈ {0,1}^n \ Range(C_s)] ≥ 2^n·2κ(n) + 2^n·ε(n)^{t(n)}` and
`Pr_s[∀ w : A(C_s, w) ∉ Range(C_s)] ≥ 1 - κ(n)`.
**Formalization Note** `A` reads the index `s`; `ε`, `κ`, `t` are functions of `n`; `ε` has no
range constraint (values outside `(0,1]` leave the statement true). -/
theorem theorem_6_6 (g : ℕ → List Bool → List Bool) (lam t : ℕ → ℕ) (ε κ : ℕ → ℝ)
(hg : ∀ n x, x.length = n - lam n → (g n x).length = n)
(hdemi : IsRelaxedDemiBitsAM g (fun n => n - lam n) ε)
(ht : ∃ b : ℕ, ∀ n, t n ≤ b * (n ^ b + 1))
(hκ : ∀ n, 0 < κ n ∧ κ n < 1)
(hlam : ∀ n, Nat.clog 2 (t n) + 1 ≤ lam n) :
¬ ∃ (A : Machine 2) (a : ℕ), IsPolyNTime A a ∧ ∀ᶠ n : ℕ in Filter.atTop,
(2 : ℝ) ^ n * (2 * κ n) + (2 : ℝ) ^ n * ε n ^ t n ≤
prob (t n * n) (AvoidDemiSucc A a g lam t n) ∧
1 - κ n ≤ prob (t n * n) (AvoidDemiSound A a g lam t 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 6.6, p.35 (PDF p.37)