scientific article; zbMATH DE number 1775455

zbMath1006.68054MaRDI QIDQ4542589

Jayram S. Thatachar

Publication date: 9 March 2003

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

branching programs

Mathematics Subject Classification ID

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

Related Items (13)

On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs ⋮ Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice ⋮ Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ Classical and Quantum Computations with Restricted Memory ⋮ The hardest halfspace ⋮ Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication ⋮ Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication ⋮ Satisfiability algorithm for syntactic read-\(k\)-times branching programs ⋮ Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs ⋮ Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs. ⋮ Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs ⋮ Time-space tradeoffs for branching programs

This page was built for publication: