CONSTANT DEPTH REDUCIBILITY

被引：174

作者：

CHANDRA, AK

STOCKMEYER, L

VISHKIN, U

机构：

[1] IBM CORP,RES LAB,DEPT COMP SCI,SAN JOSE,CA 95193

[2] NYU,COURANT INST MATH SCI,DEPT COMP SCI,NEW YORK,NY 10012

来源：

关键词：

D O I：

10.1137/0213028

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：423 / 439

页数：17

共 23 条

[11]

Hopcroft J.E., 1979, INTRO AUTOMATA THEOR

[12] SPACE-BOUNDED REDUCIBILITY AMONG COMBINATORIAL PROBLEMS [J].

JONES, ND .

[13]

Karp R.M., 1972, COMPLEXITY COMPUTER

[14]

Ladner R. E., 1975, SIGACT News, V7, P18, DOI 10.1145/990518.990519

[15] BOUNDS TO COMPLEXITIES OF NETWORKS FOR SORTING AND FOR SWITCHING [J].

MULLER, DE ;

PREPARATA, FP .

[16]

Savitch W. J., 1970, J COMPUT SYSTEM SCI, V4, P177, DOI [10.1016/S0022-0000(70)80006-X, DOI 10.1016/S0022-0000(70)80006-X]

[17]

SCHORR A, 1981, UNPUB SUPER CIRCUITS

SHILOACH, Y ;

VISHKIN, U .

[19]

Skyum S., 1981, 22nd Annual Symposium on Foundations of Computer Science, P244, DOI 10.1109/SFCS.1981.3

[20]

STOCKMEYER L, 1984, SIAM J COMP, V13, pR30