## Abstract

We introduce the tree evaluation problem, show that it is in LogDCFL (and hence in P), and study its branching program complexity in the hope of eventually proving a superlogarithmic space lower bound. The input to the problem is a rooted, balanced d-ary tree of height h, whose internal nodes are labeled with d-ary functions on [k] = {1,..., k}, and whose leaves are labeled 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. We show that the standard black pebbling algorithm applied to the binary tree of height h yields a deterministic k-way branching program with O(kh) states solving this problem, and we prove that this upper bound is tight for h = 2 and h = 3. We introduce a simple semantic restriction called thrifty on k-way branching programs solving tree evaluation problems and show that the same state bound of Θ(k ^{h}) is tight for all h ≥ 2 for deterministic thrifty programs. We introduce fractional pebbling for trees and show that this yields nondeterministic thrifty programs with Θ(kh/2+1) states solving the Boolean problem determine whether the root has value 1", and prove that this bound is tight for h = 2, 3, 4. We also prove that this same bound is tight for unrestricted nondeterministic k-way branching programs solving the Boolean problem for h = 2, 3.

Original language | English (US) |
---|---|

Article number | 4 |

Journal | ACM Transactions on Computation Theory |

Volume | 3 |

Issue number | 2 |

DOIs | |

State | Published - Jan 1 2012 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computational Theory and Mathematics

## Keywords

- Branching programs
- Log space
- LogDCFL
- Lower bounds