Width hierarchy for \(k\)-OBDD of small width

DOI10.1134/S1995080215020092zbMath1346.68092arXiv1502.04226MaRDI QIDQ748240

D. Kharzeev

Publication date: 20 October 2015

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

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

zbMATH Keywords

binary decision diagramsbranching programscomplexity classes\(k\)-OBDDOBDD

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

Very narrow quantum OBDDs and width hierarchies for classical OBDDs ⋮ On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs ⋮ Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Reordering method and hierarchies for quantum and classical ordered binary decision diagrams ⋮ On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Quantum online algorithms with respect to space and advice complexity ⋮ New size hierarchies for two way automata

Cites Work

• Unnamed Item
• Extension of the hierarchy for \(k\)-OBDDs of small width
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
• The power of nondeterminism and randomness for oblivious branching programs
• An improved hierarchy result for partitioned BDDs
• On lower bounds for read-\(k\)-times branching programs
• On the computational power of probabilistic and quantum branching program
• Branching Programs and Binary Decision Diagrams

This page was built for publication: Width hierarchy for \(k\)-OBDD of small width