Hierarchy theorems for kOBDDs and kIBDDs

被引：21

作者：

Bollig, B ^{[1
]}

Sauerhoff, M ^{[1
]}

Sieling, D ^{[1
]}

Wegener, I ^{[1
]}

机构：

[1] Univ Dortmund, FB Informatik, D-44221 Dortmund, Germany

来源：

THEORETICAL COMPUTER SCIENCE | 1998年 / 205卷 / 1-2期

关键词：

branching programs; binary decision diagrams; communication complexity; hierarchies; lower bounds;

D O I：

10.1016/S0304-3975(97)00034-0

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 1998-Elsevier Science B.V. All rights reserved.

引用

页码：45 / 60

页数：16

共 24 条

[1]

Alon N., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P410, DOI 10.1109/SFCS.1986.31

[2] MULTIPARTY PROTOCOLS, PSEUDORANDOM GENERATORS FOR LOGSPACE, AND TIME-SPACE TRADE-OFFS [J].

BABAI, L ;

NISAN, N ;

SZEGEDY, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1992, 45 (02) :204-232

[3]

BABAI L, 1995, LECT NOTES COMPUTER, V900, P361

[4]

BITNER J, 1994, FTCS-24 - THE TWENTY-FOURTH INTERNATIONAL SYMPOSIUM ON FAULT-TOLERANT COMPUTING, P266

[5]

Borodin A., 1993, Computational Complexity, V3, P1, DOI 10.1007/BF01200404

[6]

BRYANT RE, 1986, IEEE T COMPUT, V35, P677, DOI 10.1109/TC.1986.1676819

[7]

BRYANT RE, 1992, COMPUT SURV, V24, P293, DOI 10.1145/136035.136043

[8]

CHANDRA AK, 1983, 15TH P ACM STOC, P94

[9]

DAMM C, 1996, LECT NOTES COMPUTER, V1046, P643

[10]

DURIS P, 1984, 15TH P ANN ACM STOC, P81

← 1 2 3 →