On the Hierarchies for Deterministic, Nondeterministic and Probabilistic Ordered Read-k-times Branching Programs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2016
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909159965851648 |
|---|---|
| author | Khadiev, Kamil |
| author_facet | Khadiev, Kamil |
| contents | The paper examines hierarchies for nondeterministic and deterministic ordered read-$k$-times 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 $k$-times Branching programs for $k=o(\sqrt{\log{n}}/\log\log{n})$ are proved by Okolnishnikova in 1997, and for probabilistic read $k$-times Branching programs for $k\leq \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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1612_06092 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | On the Hierarchies for Deterministic, Nondeterministic and Probabilistic Ordered Read-k-times Branching Programs Khadiev, Kamil Computational Complexity The paper examines hierarchies for nondeterministic and deterministic ordered read-$k$-times 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 $k$-times Branching programs for $k=o(\sqrt{\log{n}}/\log\log{n})$ are proved by Okolnishnikova in 1997, and for probabilistic read $k$-times Branching programs for $k\leq \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. |
| title | On the Hierarchies for Deterministic, Nondeterministic and Probabilistic Ordered Read-k-times Branching Programs |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/1612.06092 |