On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs

DOI10.1134/S1995080216060159MaRDI QIDQ2361671zbMATH OpenFDO

Authors Yanyan Li

Publication date 30 June 2017

Published in Lobachevskii Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.06092

zbMATH Keywords

computational complexityhierarchybinary decision diagramsbranching programsOBDDdeterministic and nondeterministic models

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Abstract: 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}/lo{g}^{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(sqrtlogn/loglogn)$ are proved by Okolnishnikova in 1997, and for probabilistic read $k$-times Branching programs for $kleqlogn/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/logn)$. 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/logn)$. We also analyze similar hierarchies for superpolynomial and subexponential width $k$-OBDDs.

Recommendations

• On the hierarchy of nondeterministic branching k-programs
• scientific article; zbMATH DE number 1775455
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• scientific article; zbMATH DE number 1759451
• A hierarchy result for read-once branching programs with restricted parity nondeterminism
• A note on read-$k$ times branching programs
• On lower bounds for read-\(k\)-times branching programs
• scientific article; zbMATH DE number 1962823
• scientific article; zbMATH DE number 1361505
• Comparing the sizes of nondeterministic branching read-k-times programs

Cites work

• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 1500514 (Why is no real title available?)
• scientific article; zbMATH DE number 1775455 (Why is no real title available?)
• scientific article; zbMATH DE number 2102760 (Why is no real title available?)
• An improved hierarchy result for partitioned BDDs
• Branching Programs and Binary Decision Diagrams
• Communication complexity method for measuring nondeterminism in finite automata
• Extension of the hierarchy for k-OBDDs of small width
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
• Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
• On lower bounds for read-\(k\)-times branching programs
• On the computational power of probabilistic and quantum branching program
• On the hierarchy of nondeterministic branching k-programs
• Randomization and nondeterminism are comparable for ordered read-once branching programs
• The power of nondeterminism and randomness for oblivious branching programs
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Width hierarchy for \(k\)-OBDD of small width

Cited in

(13)

• scientific article; zbMATH DE number 1775455 (Why is no real title available?)
• On the hierarchy of nondeterministic branching k-programs
• Classical and Quantum Computations with Restricted Memory
• Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
• New size hierarchies for two way automata
• Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
• Error-Free Affine, Unitary, and Probabilistic OBDDs
• The power of nondeterminism and randomness for oblivious branching programs
• An improved hierarchy result for partitioned BDDs
• Extension of the hierarchy for k-OBDDs of small width
• scientific article; zbMATH DE number 1361505 (Why is no real title available?)
• Quantum online algorithms with respect to space and advice complexity
• Width hierarchy for \(k\)-OBDD of small width

This page was built for publication: On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2361671)