Theorem 1.2 (companion theorem; not used in the proof of the goal) — small-catalyst input-length tradeoff
OpenCatalyticTreeEval.Main.Supplement.theorem_1_2complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1tree-evaluation
For every positive binary-tree height and label length and every unrestricted full truth-table instance of serialized length , there is one deterministic machine whose simultaneous resources, with positive-log conventions , satisfy
It outputs the entire root label and restores every arbitrary catalytic bit. This is the companion small-catalyst tradeoff; Corollary 4.8 supplies its parameterized support, and small valid inputs are included. The catalyst is bounded by a prefix of each longer arbitrary tape, with whole-tape restoration.
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: log n, log log n and log log log n in asymptotic bounds → L(n)=1+log₂(n+1), L₂(n)=1+log₂ L(n), L₃(n)=1+log₂ L₂(n), with n the full serialized input length; reason: positive-log conventions preserve the stated asymptotics and include every small valid input
Preamble
import Definitions.Def_CatalyticTreeEval_Main_Supplement_UniformConstructions set_option autoImplicit false
Formal statement
namespace CatalyticTreeEval.Main.Supplement
theorem theorem_1_2 :
∃ (M : Machine) (Cs Cc Ct : ℝ), 0 < Cs ∧ 0 < Cc ∧ 0 < Ct ∧
∀ h l : ℕ, 0 < h → 0 < l → ∀ I : Tree l h,
let n := I.encode.length
ComputesPrefix M I.encode (bits l I.value.val)
(Cs * lg n * Real.sqrt (loglog n) * logloglog n)
(exp₂ (exp₂ (Cc * Real.sqrt (loglog n))))
(((n : ℝ) + 1) ^ (Ct * Real.sqrt (loglog n))) := 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, Theorem 1.2, printed p. 1 (PDF p. 3)