Read-Once Branching Programs for Tree Evaluation Problems

摘要

Toward the ultimate goal of separating L and P, Cook, McKenzie, Wehr, Braverman and Santhanam introduced the tree evaluation problem (TEP). For fixed h, k>0, FT_h(k) is given as a complete, rooted binary tree of height h, in which each internal node is as