Theorem 7.2 — no targeted HSG with few outputs against coNP linear time
OpenAvoidPlast.Supplement.theorem_7_2complexity-theoryderandomizationhitting-set-generatorsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1range-avoidancespace-bounded-computation
Let , (so is a power of two) with , and let be the class of co-non-deterministic linear-time machines using bits of randomness on inputs of length . Assume that every non-deterministic machine fails to solve Avoid on some circuit of size , that is, rejects all witnesses or outputs on some witness a string in the range of . Then there is no SearchNP-computable targeted -HSG against that on -bit inputs has seed length and output length .
Under worst-case hardness of Avoid this answers Goldreich's question negatively for generators with few outputs.
Differences from the source:
- generalization: "for every non-deterministic machine " → for every non-deterministic polynomial-time machine ; reason: a weaker hypothesis; the proof applies it only to the polynomial-time algorithm built from the generator
- reading: "there is ... of size " → for infinitely many there is an -bit circuit description; reason: matches " sufficiently large" in Definition 7.1
- encoding: " of size " → an -bit description under the fixed-width encoding
decodeCircuit; reason: the paper fixes no encoding; this one is linear-time parseable, as the proof's distinguisher needs - encoding: with a power of two → and seed length ; reason: the same parameters
- reading: , , → required for every sufficiently large ; reason: at the constraint is unsatisfiable, so "for every " would make the theorem vacuous
- encoding: co-non-deterministic linear-time machines using random bits → a machine halting within steps for ; iff every with is accepted; reason: Definition 3.7 with a linear time bound
- reading: a SearchNP-computable targeted HSG (Definition 7.1 extended to non-deterministic ) → on every input some witness is accepted, every accepting path outputs strings of bits, and for large every accepting path hits every with ; reason: Definition 7.1 and the proof: "for every there is a witness causing to output a list"
Preamble
import Mathlib import Definitions.Def_AvoidPlast_Accepts import Definitions.Def_AvoidPlast_HaltsWithin import Definitions.Def_AvoidPlast_Machine import Definitions.Def_AvoidPlast_output import Definitions.Def_AvoidPlast_Supplement_IsPolyNTime import Definitions.Def_AvoidPlast_Supplement_Circuit import Definitions.Def_AvoidPlast_Supplement_Circuit_eval import Definitions.Def_AvoidPlast_Supplement_decodeCircuit import Definitions.Def_AvoidPlast_Supplement_coNDAccepts import Definitions.Def_AvoidPlast_Supplement_IsSearchNPGen import Definitions.Def_AvoidPlast_Supplement_HitsTargeted
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 7.2 (Li–Tell, *Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance*, STOC 2027 submission manuscript (sha256 e1ff3a9e…d6728), p.40). Let `m(n) < n`, `k(n) = m(n)·2^{j(n)} < n` (so `k/m = 2^j` is a power
of two) with `j + 1 < m`, and let `D` be the class of co-non-deterministic linear-time machines
using `m(n)` random bits. Assume that every non-deterministic (polynomial-time) machine `M` fails to
solve Avoid on some circuit `C : {0,1}^{m - j - 1} → {0,1}^k` of size `n`, i.e. `M(C)` rejects all
witnesses or outputs on some witness a string in the range of `C`. Then there is no
SearchNP-computable targeted `(1/2)`-HSG against `D` that on `n`-bit inputs has seed length `j`
(`2^j` outputs) and output length `m`.
**Formalization Note** "Size `n`" is an `n`-bit description under `decodeCircuit`; the assumption is
required for infinitely many `n`, matching "sufficiently large `n`" in Definition 7.1. The parameter
constraints are required for every sufficiently large `n` (at `n = 0`, `m(n) < n` is impossible). -/
theorem theorem_7_2 (m j : ℕ → ℕ)
(hmk : ∀ᶠ n : ℕ in Filter.atTop, m n < n ∧ m n * 2 ^ j n < n ∧ j n + 1 < m n)
(hyp : ∀ (M : Machine 2) (a : ℕ), IsPolyNTime M a → ∃ᶠ n : ℕ in Filter.atTop,
∃ c : List Bool, c.length = n ∧ ∃ circ : Circuit, decodeCircuit c = some circ ∧
circ.nIn = m n - j n - 1 ∧ circ.outs.length = m n * 2 ^ j n ∧
((∀ w : List Bool, w.length ≤ a * (n ^ a + 1) → ¬ Accepts M ![c, w]) ∨
∃ w : List Bool, w.length ≤ a * (n ^ a + 1) ∧ Accepts M ![c, w] ∧
∃ z : List Bool, z.length = circ.nIn ∧ circ.eval z = output M ![c, w])) :
¬ ∃ (H : Machine 2) (a : ℕ), IsSearchNPGen H a (fun n => 2 ^ j n) m ∧
∀ (D : Machine 3) (K : ℕ),
(∀ x r w : List Bool, r.length = m x.length → HaltsWithin D ![x, r, w] (K * (x.length + 1))) →
HitsTargeted H a (fun n => 2 ^ j n) m (fun x r => coNDAccepts D (K * (x.length + 1)) x r)
(1 / 2) := 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 7.2, p.40 (PDF p.42)