Pebbling and Branching Programs Solving the Tree Evaluation Problem

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Written as one of the requirements for my MSc. 29 pages, 6 figures

Scientific paper

We study restricted computation models related to the Tree Evaluation Problem}. The TEP was introduced in earlier work as a simple candidate for the (*very*) long term goal of separating L and LogDCFL. The input to the problem is a rooted, balanced binary tree of height h, whose internal nodes are labeled with binary functions on [k] = {1,...,k} (each given simply as a list of k^2 elements of [k]), and whose leaves are labeled with elements of [k]. Each node obtains a value in [k] equal to its binary function applied to the values of its children, and the output is the value of the root. The first restricted computation model, called Fractional Pebbling, is a generalization of the black/white pebbling game on graphs, and arises in a natural way from the search for good upper bounds on the size of nondeterministic branching programs (BPs) solving the TEP - for any fixed h, if the binary tree of height h has fractional pebbling cost at most p, then there are nondeterministic BPs of size O(k^p) solving the height h TEP. We prove a lower bound on the fractional pebbling cost of d-ary trees that is tight to within an additive constant for each fixed d. The second restricted computation model we study is a semantic restriction on (non)deterministic BPs solving the TEP - Thrifty BPs. Deterministic (resp. nondeterministic) thrifty BPs suffice to implement the best known algorithms for the TEP, based on black (resp. fractional) pebbling. In earlier work, for each fixed h a lower bound on the size of deterministic thrifty BPs was proved that is tight for sufficiently large k. We give an alternative proof that achieves the same bound for all k. We show the same bound still holds in a less-restricted model, and also that gradually weaker lower bounds can be obtained for gradually weaker restrictions on the model.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Pebbling and Branching Programs Solving the Tree Evaluation Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pebbling and Branching Programs Solving the Tree Evaluation Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pebbling and Branching Programs Solving the Tree Evaluation Problem will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-379083

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.