The Tree Evaluation Problem was introduced by 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.
Some work has been done in the more general DAG Evaluation Problem, where the underlying graph is an arbitrary DAG rather than a complete binary tree. Wehr @cite_9 proved an analogous lower bound for deterministic thrifty branching programs solving DAG Evaluation. Chan @cite_6 , using different pebble games, studied circuit depth lower bounds for DAG Evaluation under a semantic restriction called output-relevance, closely related to thriftiness. Because of the more general nature of DAG Evaluation, Chan achieved a separation of @math and @math for each @math , as well as separating and , under this semantic restriction.
@cite_9 @cite_6
1626365820 1660848351
We answer a problem posed in (G 'al, Kouck 'y, McKenzie 2008) regarding a restricted model of small-space computation, tailored for solving the GEN problem. They define two variants of "incremental branching programs", the syntactic variant defined by a restriction on the graph-theoretic paths in the program, and the more-general semantic variant in which the same restriction is enforced only on the consistent paths - those that are followed by at least one input. They show that exponential size is required for the syntactic variant, but leave open the problem of superpolynomial lower bounds for the semantic variant. Here we give an exponential lower bound for the semantic variant by generalizing lower bound arguments, from earlier work, for a similar restricted model tailored for solving a special case of GEN called Tree Evaluation. We study the connection between pebble games and complexity. First, we derive complexity results using pebble games. It is shown that three pebble games used for studying computational complexity are equivalent: namely, the two-person pebble game of Dymond-Tompa, the two-person pebble game of Raz-McKenzie, and the one-person reversible pebble game of Bennett have the same pebble costs over any directed acyclic graph. The three pebble games have been used for studying parallel complexity and for proving lower bounds under restricted settings, and we show one more such lower bound on circuit-depth. Second, the pebble costs are applied to proof complexity. Concerning a family of unsatisfiable CNFs called pebbling contradictions, the pebble cost in any of the pebble games controls the scaling of some parameters of resolution refutations. Namely, the pebble cost controls the minimum depth of resolution refutations and the minimum size of tree-like resolution refutations. Finally, we study the space complexity of computing the pebble costs and of computing the minimum depth of resolution refutations. It is PSPACE-complete to compute the pebble cost in any of the three pebble games, and to compute the minimum depth of resolution refutations.