Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling

Vahid R. Asadi, Richard Cleve

The Tree Evaluation Problem ($\mathsf{TreeEval}$) is a computational problem originally proposed as a candidate to prove a separation between complexity classes $\mathsf{P}$ and $\…