Journal
LOBACHEVSKII JOURNAL OF MATHEMATICS
Volume 37, Issue 6, Pages 683-704Publisher
MAIK NAUKA/INTERPERIODICA/SPRINGER
DOI: 10.1134/S1995080216060159
Keywords
Branching programs; Binary decision diagrams; OBDD; deterministic and nondeterministic models; hierarchy; computational complexity
Categories
Ask authors/readers for more resources
The paper examines hierarchies for nondeterministic and deterministic ordered read-ktimes Branching programs. The currently known hierarchies for deterministic k-OBDD models of Branching programs for k = o(n (1/2)/log(3/2) n) are proved by B. Bollig, M. Sauerhoff, D. Sieling, and I. Wegener in 1998. Their lower bound technique was based on communication complexity approach. For nondeterministic k-OBDD it is known that, if k is constant then polynomial size k-OBDD computes same functions as polynomial size OBDD (The result of Brosenne, Homeister and Waack, 2006). In the same time currently known hierarchies for nondeterministic read ktimes Branching programs for are proved by Okolnishnikova in 1997, and for probabilistic read k-times Branching programs for k aecurrency sign log n/3 are proved by Hromkovic and Saurhoff in 2003. We show that increasing k for polynomial size nodeterministic k-OBDD makes model more powerful if k is not constant. Moreover, we extend the hierarchy for probabilistic and nondeterministic k-OBDDs for k = o(n/log n). These results extends hierarchies for read k-times Branching programs, but k-OBDD has more regular structure. The lower bound techniques we propose are a functional description of Boolean function presented by nondeterministic k-OBDD and communication complexity technique. We present similar hierarchies for superpolynomial and subexponential width nondeterministic k-OBDDs. Additionally we expand the hierarchies for deterministic k-OBDDs using our lower bounds for k = o(n/log n). We also analyze similar hierarchies for superpolynomial and subexponential width k-OBDDs.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available