OPTIMAL BOUNDS FOR DECISION-PROBLEMS ON THE CRCW PRAM

被引：65

作者：

BEAME, P ^{[1
]}

HASTAD, J ^{[1
]}

机构：

[1] ROYAL INST TECHNOL,S-10044 STOCKHOLM 70,SWEDEN

来源：

JOURNAL OF THE ACM | 1989年 / 36卷 / 03期

关键词：

D O I：

10.1145/65950.65958

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

引用

页码：643 / 670

页数：28

共 16 条

[1] SIGMA-11-FORMULAE ON FINITE STRUCTURES [J].

AJTAI, M .

ANNALS OF PURE AND APPLIED LOGIC, 1983, 24 (01) :1-48

[2] LIMITS ON THE POWER OF CONCURRENT-WRITE PARALLEL MACHINES [J].

BEAME, P .

INFORMATION AND COMPUTATION, 1988, 76 (01) :13-28

[3]

BEAME P, 1985, LOWER BOUNDS VERY PO

[4]

BEAME P, 1987, 19TH P ACM S THEOR C, P83

[5]

BEAME PW, 1986, TR19887 U TOR

[6]

Bollobas B., 1985, RANDOM GRAPHS

[7] CONSTANT DEPTH REDUCIBILITY [J].

CHANDRA, AK ;

STOCKMEYER, L ;

VISHKIN, U .

SIAM JOURNAL ON COMPUTING, 1984, 13 (02) :423-439

[8]

Erdos P., 1974, PROBABILISTIC METHOD

[9] PARITY, CIRCUITS, AND THE POLYNOMIAL-TIME HIERARCHY [J].

FURST, M ;

SAXE, JB ;

SIPSER, M .

MATHEMATICAL SYSTEMS THEORY, 1984, 17 (01) :13-27

[10]

Hastad Johan, 1987, COMPUTATIONAL LIMITA

← 1 2 →