2013/11/01 by Liu, David
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1311.0293
The Tree Evaluation Problem was introduced by Cook et al. in 2010 as a candidate for separating P from L and NL. The most general space lower bounds known for the Tree Evaluation Problem require a semantic restriction on the branching programs and use a connection to well-known pebble games to generate a bottleneck argument. These bounds are met by corresponding upper bounds generated by natural implementations of optimal pebbling algorithms. In this paper we extend these ideas to a variety of restricted families of both deterministic and non-deterministic branching programs, proving tight lower bounds under these restricted models. We also survey and unify known lower bounds in our "pebbling argument" framework.