Theorem 7.3 — the low-space analogue of Theorem 7.2
OpenAvoidPlast.Supplement.theorem_7_3complexity-theoryderandomizationhitting-set-generatorsp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidancespace-bounded-computation
Let , and . Let be a -evaluable indexed family such that , and let be the class of co-non-deterministic machines running in simultaneous time and space and using bits of randomness. Then there is no SearchNP-computable targeted -HSG against that on -bit inputs has seed length and output length .
The paper omits the proof as essentially the same as that of Theorem 7.2.
Differences from the source:
- reading: , → required for every sufficiently large ; reason: at the constraint is unsatisfiable, so "for every " would make the theorem vacuous
- reading: → a non-deterministic polynomial-time machine solves on every input of every sufficiently large length; reason: solutions need not exist for short inputs, where the constraints fail; as in Theorem 6.1
- reading: co-non-deterministic machines of space → the co-non-deterministic choices are read once (one-way tape); the random string is read-only; reason: the usual convention for space-bounded non-determinism; the term in the space bound is the cost of storing the guessed input
- encoding: time , space → time , work space , co-non-deterministic choices of length at most the time bound; reason: reading R2
- encoding: ; a power of two → ; ; reason: the same parameters
Preamble
import Mathlib import Definitions.Def_AvoidPlast_EvaluableInSpace import Definitions.Def_AvoidPlast_HaltsWithin import Definitions.Def_AvoidPlast_Machine import Definitions.Def_AvoidPlast_workSpace import Definitions.Def_AvoidPlast_Supplement_IsPolyNTime import Definitions.Def_AvoidPlast_Supplement_SolvesAvoidNDB import Definitions.Def_AvoidPlast_Supplement_coNDAccepts import Definitions.Def_AvoidPlast_Supplement_IsSearchNPGen import Definitions.Def_AvoidPlast_Supplement_HitsTargeted import Definitions.Def_AvoidPlast_Supplement_OneWayTape
Formal statement
namespace AvoidPlast.Supplement
open AvoidPlast
/-- Theorem 7.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.40), the low-space analogue of Theorem 7.2. Let `S(n) ≥ log n`,
`m(n) ≤ k(n) = m(n)·2^{j(n)} < n` and `ℓ = m - j - 1 > 0`, and let `C[ℓ → k]` be a
`SPACE(S(n))`-evaluable indexed family with `Avoid_C ∉ SearchNP`. Let `D` be the class of
co-non-deterministic machines running in simultaneous time `2^{O(S(n))}` and space `O(S(n) + ℓ(n))`
and using `m(n)` random bits. Then there is no SearchNP-computable targeted `(1/2)`-HSG against `D`
that on `n`-bit inputs has seed length `j` and output length `m`.
**Formalization Note** The co-non-deterministic choices are read once (`OneWayTape`), the usual
convention for space-bounded non-determinism; the random string is read-only. `Avoid_C ∈ SearchNP`
is solvability on every input of every sufficiently large length, as in Theorem 6.1. -/
theorem theorem_7_3 (S : ℕ → ℝ) (hS : ∀ n : ℕ, Real.logb 2 n ≤ S n) (m j : ℕ → ℕ)
(hmk : ∀ᶠ n : ℕ in Filter.atTop, m n * 2 ^ j n < n ∧ j n + 1 < m n)
(C : List Bool → List Bool → List Bool)
(hC : EvaluableInSpace C (fun n => m n - j n - 1) (fun n => m n * 2 ^ j n) S)
(hAv : ¬ ∃ (M : Machine 2) (a : ℕ), IsPolyNTime M a ∧ ∀ᶠ n : ℕ in Filter.atTop,
∀ x : List Bool, x.length = n →
SolvesAvoidNDB M C (fun n => m n - j n - 1) (fun n => m n * 2 ^ j n)
(fun n => a * (n ^ a + 1)) x) :
¬ ∃ (H : Machine 2) (a : ℕ), IsSearchNPGen H a (fun n => 2 ^ j n) m ∧
∀ (D : Machine 3) (K : ℕ), OneWayTape D 2 →
(∀ x r w : List Bool, r.length = m x.length →
HaltsWithin D ![x, r, w] ⌈(2 : ℝ) ^ (K * (S x.length + 1))⌉₊ ∧
(workSpace D ![x, r, w] : ℝ) ≤ K * (S x.length + (m x.length - j x.length - 1 : ℕ) + 1)) →
HitsTargeted H a (fun n => 2 ^ j n) m
(fun x r => coNDAccepts D ⌈(2 : ℝ) ^ (K * (S 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.3, p.40 (PDF p.42)