Catalytic approaches to the tree evaluation problem

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. (While the original problem allows an arbitrary-degree tree, we focus on binary trees.) 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 2 h −1 layers of width up to k h . Until now no better deterministic algorithm was known.