期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-10
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The study of branching programs for the Tree Evaluation Problem (TreeEval), introduced by S. Cook et al. (TOCT 2012), remains one of the most promising approaches to separating L from P. Given a label in [k] at each leaf of a complete binary tree and an explicit function in [k] 2 → [k] for recursively computing the value of each internal node from its children, the problem is to compute the value at the root node. The problem is parameterized by the alphabet size k and the height h of the tree. A branching program implementing the straightforward recursive algorithm uses Θ((k 1)h ) states, organized into 2h −1 layers of width up to k h . Until now no better deterministic algorithm was known. We present a series of three new algorithms solving TreeEval. They are inspired by the work of Buhrman et al. on catalytic space (STOC 2012), applied outside the catalytic-space setting. First we give a novel branching program with 24h poly(k) layers of width 23k , which beats the straightforward algorithm when h = ω(k/ log k). Next we give a branching program with k 2h poly(k) layers of width k 3 . This has total size comparable to the straightforward algorithm, but is implemented using the catalytic framework. Finally we interpolate between the two algorithms to give a branching program with (O( k h ))2h poly(k) layers of width (O( k h ))ϵh for any constant ϵ > 0, which beats the straightforward algorithm for all h ≥ k 1/2 poly ϵ . These are the first deterministic branching programs to beat the straightforward algorithm, but more importantly this is the first non-trivial approach to proving deterministic upper bounds for TreeEval. We also contribute new machinery to the catalytic computing program, which may be of independent interest to some readers.
