Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TREE EVALUATION PROBLEM:
Reports tagged with tree evaluation problem:
TR20-056 | 17th April 2020
James Cook, Ian Mertz

#### Catalytic Approaches to the Tree Evaluation Problem

The study of branching programs for the Tree Evaluation Problem, 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 \to ... more >>>

ISSN 1433-8092 | Imprint