THE MONOTONE CIRCUIT COMPLEXITY OF BOOLEAN FUNCTIONS

被引：180

作者：

ALON, N

BOPPANA, RB

机构：

[1] TEL AVIV UNIV, DEPT MATH, IL-69978 TEL AVIV, ISRAEL

[2] IBM CORP, ALMADEN RES CTR, SAN JOSE, CA 95120 USA

[3] MIT, COMP SCI LAB, CAMBRIDGE, MA 02139 USA

来源：

关键词：

D O I：

10.1007/BF02579196

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

引用

页码：1 / 22

页数：22

共 18 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st

[2]

Andreev A.E., 1985, SOV MATH DOKL, V31, P530

[3]

BLONIARZ PA, 1979, MIT238 LAB COMP SCI

[4] A BOOLEAN FUNCTION REQUIRING 3N NETWORK SIZE [J].

BLUM, N .

[5]

CHUNG F, 1984, SIGACT NEWS, V16, P46

[6]

Erdos P., 1960, J LOND MATH SOC, V35, P85, DOI DOI 10.1112/JLMS/S1-35.1.85

[7]

Hopcroft J. E., 1973, SIAM Journal on Computing, V2, P225, DOI 10.1137/0202019

[8] MONOTONE SWITCHING CIRCUITS AND BOOLEAN MATRIX PRODUCT [J].

MEHLHORN, K ;

GALIL, Z .

[9]

Nesetril J., 1985, COMM MATH U CAROL, V26, P415

[10]

Paterson M. S., 1975, Theoretical Computer Science, V1, P13, DOI 10.1016/0304-3975(75)90009-2