Corollary 4.8 (used in the proof of Theorem 1.2) — parameterized small-catalyst tradeoff
OpenCatalyticTreeEval.Main.Supplement.corollary_4_8complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1tree-evaluation
For all heights and all label lengths above one absolute threshold, one deterministic machine evaluates every binary tree with arbitrary full truth tables. It outputs all root bits and restores every bit of every initially arbitrary catalytic tape. With uniform positive constants, its simultaneous resources are
This parameterized tradeoff supports Theorem 1.2. The catalyst predicate holds for every tape at least as long as the ceiling of the displayed bound, restores the whole tape, and never reaches the right end of the permitted prefix.
Differences from the source:
- encoding: asymptotic algorithmic resource bounds → a finite binary machine and positive uniform constants, with fixed polynomial degrees where needed; reason: expands O/poly using actual transitions and visited work cells; constants precede varying inputs and tapes
- encoding: ℓ larger than a sufficiently large absolute constant → one existential integer threshold L≥4 and L≤ℓ; reason: avoids undefined iterated logarithms; taking an integer ceiling and increasing an unspecified threshold preserves the source domain
Preamble
import Definitions.Def_CatalyticTreeEval_Main_Resources set_option autoImplicit false
Formal statement
namespace CatalyticTreeEval.Main.Supplement
theorem corollary_4_8 :
∃ (M : Machine) (Cs Cc Ct : ℝ) (L : ℕ),
0 < Cs ∧ 0 < Cc ∧ 0 < Ct ∧ 4 ≤ L ∧
∀ h l : ℕ, 0 < h → L ≤ l → ∀ I : Tree l h,
ComputesPrefix M I.encode (bits l I.value.val)
(Cs * (l + h * Real.sqrt (log₂ l) * log₂ (log₂ l)))
(exp₂ (exp₂ (Cc * Real.sqrt (log₂ l))))
(exp₂ (Ct * (l + h * Real.sqrt (log₂ l)))) := by sorry
end CatalyticTreeEval.Main.Supplement
Source
Alexandra Henzinger, Edward Pyne, Seyoon Ragavan, Catalytic Tree Evaluation from Matching Vectors, STOC 2027 submission #533 (October 2026), canonical source.pdf SHA-256 17c3a71f0fb5afe2456558477e16fbac4200191e6e68f0facf212e24cb4ef238, Corollary 4.8, printed p. 27 (PDF p. 29)