Almost the same types of restricted branching programs (orbinary decision diagrams BDDs) are considered in complexitytheory and in applications like hardware verification. Thesemodels are read-once branching programs (free BDDs) and certaintypes of oblivious branching programs (ordered and indexed BDDswith k layers). The complexity of the satisfiability problemfor these restricted branching programs is investigated andtight hierarchy results are proved for the classes of functionsrepresentable by k layers of ordered or indexed BDDs ofpolynomial size.
展开▼
