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

DOI10.1134/S1995080216060159zbMATH Open1409.68105arXiv1612.06092MaRDI QIDQ2361671FDOQ2361671

Authors: Yanyan Li 

Publication date: 30 June 2017

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

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.

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

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

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)

Cites Work

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

Cited In (13)

• 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
• Title not available (Why is that?)
• Quantum online algorithms with respect to space and advice complexity
• Width hierarchy for \(k\)-OBDD of small width
• Title not available (Why is that?)
• On the hierarchy of nondeterministic branching k-programs
• Classical and Quantum Computations with Restricted Memory

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)