Theorem 5.3 — classical collision time-space tradeoff
OpenCompressedOracleDuality.LabelSymmetric.Supplement.theorem_5_3There is one universal real constant such that the following holds for every , every natural space and query bounds and , and every deterministic label-symmetric collision branching program with at most vertices in each internal layer. Terminal output leaves have no width bound, and transitions may merge. Set . If the actual output reports an ordered triple with and with probability at least , averaged uniformly over all functions , then
The same constant works for every program, output map, size, time bound, and space bound. All query counts are covered, without a restriction such as or . Neither matched-label nor progress estimates are hypotheses. This is the independent classical companion theorem; it is not used in the proof of the mission's quantum goal.
Differences from the source:
- encoding: one carrier [N] for inputs and labels → published Fin (2^n) inputs and n-bit labels, identified by the fixed most-significant-bit-first bijection e; reason: e transports every oracle and label permutation bijectively; input ordering is the published strict order
- encoding: a singleton start layer, exactly 2^S internal vertices, and arbitrarily many terminal leaves → finite layer types with a Unique initial layer and at most 2^S vertices only for 1 <= t < T; reason: padding unreachable internal vertices recovers the printed width without altering executions, symmetry, or success; T=0 retains one fixed output
- encoding: TS = Omega(N log N), with the standing N >= 64 and S >= log_2 N → a single existential c>0 before n,S,T,B, with c2^nn <= T*S for every n>=6 and S>=n; reason: this expands the asymptotic bound uniformly over all algorithms and includes every standing size regime; log_2(2^n)=n
import Definitions.Def_CompressedOracleDuality_LabelSymmetric_Supplement_ClassicalModel
namespace CompressedOracleDuality.LabelSymmetric.Supplement
/-- Theorem 5.3, (79), p.27: one constant before every size, space, time, and program.
No matched-label or progress bound is a hypothesis of this theorem. -/
theorem theorem_5_3 :
∃ c : ℝ, 0 < c ∧ ∀ (n S T : ℕ) (B : ClassicalProgram n T),
6 ≤ n → n ≤ S → B.SpaceBound S → ClassicalLabelSymmetric B →
(2 : ℝ) / 3 ≤ classicalSuccess B →
c * (2 : ℝ) ^ n * (n : ℝ) ≤ (T : ℝ) * (S : ℝ) := by sorry
end CompressedOracleDuality.LabelSymmetric.Supplement