Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR94-026 | 12th December 1994 00:00

On the Power of Different Types of Restricted Branching Programs

RSS-Feed

Abstract:


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