Fractional Pebbling and Thrifty Branching Programs

Abstract

We study the branching program complexity of the {\em tree evaluation problem},
introduced in \cite{BrCoMcSaWe09} as a candidate for separating \nl\ from\logcfl.  The input to the problem is a rooted, balanced $d$-ary tree of height$h$, whose internal nodes are labelled with $d$-ary functions on$[k]=\{1,\ldots,k\}$, and whose leaves are labelled with elements of $[k]$.Each node obtains a value in $[k]$ equal to its $d$-ary function applied to the values of its $d$ children.  The output is the value of the root.

Deterministic $k$-way branching programs as related to black pebbling algorithms have been studied in \cite{BrCoMcSaWe09}. Here we introduce the notion of {\em fractional pebbling} of graphs to study non-deterministicbranching program size. We prove that this yields non-deterministic branching
programs with $\Theta(k^{h/2+1})$ states solving the Boolean problem ``determine whether the root has value 1'' for binary trees - this isasymptotically better than the branching program size corresponding toblack-white pebbling. We prove upper and lower bounds on the fractionalpebbling number of $d$-ary trees, as well as a general result relating thefractional pebbling number of a graph to the black-white pebbling number.

We introduce a simple semantic restriction called {\em thrifty} on $k$-way branching programs solving tree evaluation problems and show that the branchingprogram size bound of $\Theta(k^h)$ is tight (up to a constant factor) for all
$h\ge 2$ for deterministic thrifty programs.  We show that thenon-deterministic branching programs that correspond to fractional pebbling are
thrifty as well, and that the bound of $\Theta(k^{h/2+1})$ is tight for
non-deterministic thrifty programs for $h=2,3,4$. We hypothesise that thrifty
branching programs are optimal among $k$-way branching programs solving the
tree evaluation problem - proving this for deterministic programs would
separate \lspace\ from \logcfl\, and proving it for non-deterministic programs
would separate \nl\ from \logcfl.