HIERARCHY THEOREMS FOR KOBDDS AND KIBDDS

Almost the same types of restricted branching programs (or binary deci sion diagrams BDDs) are considered in complexity theory and in applica tions like hardware verification. These models are read-once branching programs (free BDDs) and certain types of oblivious branching program s (ordered and indexed BDDs with k layers). The complexity of the sati sfiability problem for these restricted branching programs is investig ated and tight hierarchy results are proved for the classes of functio ns representable by k layers of ordered or indexed BDDs of polynomial size. (C) 1998-Elsevier Science B.V. All rights reserved.