License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.409
URN: urn:nbn:de:0030-drops-44756
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4475/
Iwama, Kazuo ;
Nagao, Atsuki
Read-Once Branching Programs for Tree Evaluation Problems
Abstract
Toward the ultimate goal of separating L and P, Cook, McKenzie, Wehr, Braverman and Santhanam introduced the tree evaluation problem (TEP). For fixed h, k>0, FT_h(k) is given as a complete, rooted binary tree of height h, in which each internal node is associated with a function from [k]^2 to [k], and each leaf node with a number in [k]. The value of an internal node v is defined naturally, i.e., if it has a function f and the values of its two child nodes are a and b, then the value of v is f(a,b). Our task is to compute the value of the root node by sequentially executing this function evaluation in a bottom-up fashion. The problem is obviously in P and if we could prove that any branching program solving FT_h(k) needs at least k^(r(h)) states for any unbounded function r, then this problem is not in L, thus achieving our goal. The above authors introduced a restriction called thrifty against the structure of BP’s (i,e., against the algorithm for solving the problem) and proved that any thrifty BP needs Omega(k^h) states. This paper proves a similar lower bound for read-once branching programs, which allows us to get rid of the restriction on the order of nodes read by the BP that is the nature of the thrifty restriction.
BibTeX - Entry
@InProceedings{iwama_et_al:LIPIcs:2014:4475,
author = {Kazuo Iwama and Atsuki Nagao},
title = {{Read-Once Branching Programs for Tree Evaluation Problems}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {409--420},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-65-1},
ISSN = {1868-8969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4475},
URN = {urn:nbn:de:0030-drops-44756},
doi = {10.4230/LIPIcs.STACS.2014.409},
annote = {Keywords: Lower bounds, Branching Programs, Read-Once Branching Programs, Space Complexity, Combinatorics}
}
|
Keywords: |
|
Lower bounds, Branching Programs, Read-Once Branching Programs, Space Complexity, Combinatorics |
|
Collection: |
|
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) |
|
Issue Date: |
|
2014 |
|
Date of publication: |
|
05.03.2014 |
