Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR94-026 | 12th December 1994 00:00

On the Power of Different Types of Restricted Branching Programs



Almost the same types of restricted branching programs (or
binary decision diagrams BDDs) are considered in complexity
theory and in applications like hardware verification. These
models are read-once branching programs (free BDDs) and certain
types of oblivious branching programs (ordered and indexed BDDs
with k layers). The complexity of the satisfiability problem
for these restricted branching programs is investigated and
tight hierarchy results are proved for the classes of functions
representable by k layers of ordered or indexed BDDs of
polynomial size.

ISSN 1433-8092 | Imprint