Theorem 6.5 — Ilango's hardness of Avoid for zero-error non-deterministic algorithms
OpenAvoidPlast.Supplement.theorem_6_5average-case-complexitycomplexity-theorydemi-bitsp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computation
For , let be an -demi-bits generator against with , and for let . There is no non-deterministic polynomial-time machine (allowed to output ) that satisfies, for every sufficiently large , over uniform :
- completeness: ;
- soundness: .
The paper gives a new proof through the covering lemma (Lemma 6.4).
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 "
- reading: -demi-bits ( not said to be a constant or a function of ) → , any function of , no range constraint; reason: with constant and fixed the threshold exceeds and the theorem is empty, so depends on ; values outside make the demi-bits hypothesis false or the completeness threshold unattainable, so no range hypothesis is needed (trap 36)
- encoding: represented in bits (codes not specified) → least significant bit first; codes mapped to ; reason: the convention of Theorem 6.6; it does not change
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_IsDemiBitsNP
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 6.5, Ilango's result [Ila25, Theorem 3.3, Corollary 3.7] with a new proof (Li–Tell, *Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance*, STOC 2027 submission manuscript (sha256 e1ff3a9e…d6728),
p.34). For `t ∈ ℕ`, let `g_n : {0,1}^{n - λ(n)} → {0,1}^n` be an `ε`-demi-bits generator against NP
with `λ(n) ≥ ⌈log t⌉ + 130`, and `C_s(x, i) = g(x) ⊕ s_i` for `s ∈ {0,1}^{t×n}`. 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·ε(n)^t` and
`Pr_s[∀ w : A(C_s, w) ∉ Range(C_s)] = 1`.
**Formalization Note** `ε` is a real function of `n` with no range constraint (for a constant
`ε < 1` the threshold `2^n ε^t` exceeds `1`; values outside `(0,1]` leave the statement true).
`A` reads the index `s`. -/
theorem theorem_6_5 (t : ℕ) (g : ℕ → List Bool → List Bool) (lam : ℕ → ℕ) (ε : ℕ → ℝ)
(hg : ∀ n x, x.length = n - lam n → (g n x).length = n)
(hdemi : IsDemiBitsNP g (fun n => n - lam n) ε)
(hlam : ∀ n, Nat.clog 2 t + 130 ≤ lam n) :
¬ ∃ (A : Machine 2) (a : ℕ), IsPolyNTime A a ∧ ∀ᶠ n : ℕ in Filter.atTop,
(2 : ℝ) ^ n * ε n ^ t ≤ prob (t * n) (AvoidDemiSucc A a g lam (fun _ => t) n) ∧
prob (t * n) (AvoidDemiSound A a g lam (fun _ => t) n) = 1 := 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.5, p.34 (PDF p.36)