LOWER BOUNDS ON PROBABILISTIC LINEAR DECISION TREES

被引：48

作者：

SNIR, M

机构：

来源：

THEORETICAL COMPUTER SCIENCE | 1985年 / 38卷 / 01期

关键词：

D O I：

10.1016/0304-3975(85)90210-5

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：69 / 82

页数：14

共 10 条

[1] COMPLEXITY OF COMPUTATIONS UNDER VARYING SETS OF PRIMITIVES [J].

DOBKIN, DP ;

LIPTON, RJ .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1979, 18 (01) :86-91

[2]

Farkas J, 1902, J REINE ANGEW MATH, V124, P1

[3] COMPLEXITY OF COMPUTING MEASURE OF U[AI, BI] [J].

FREDMAN, ML ;

WEIDE, B .

COMMUNICATIONS OF THE ACM, 1978, 21 (07) :540-544

[4]

HOLADAY JC, 1957, CONTRIBUTIONS THEORY, V3, P189

[5] FINDING MAXIMA OF A SET OF VECTORS [J].

KUNG, HT ;

LUCCIO, F ;

PREPARATA, FP .

JOURNAL OF THE ACM, 1975, 22 (04) :469-476

[6]

Manber U, 1982, 14 ANN ACM S THEOR C, P234, DOI [10.1145/800070.802197, DOI 10.1145/800070.802197]

[7] OPTIMALITY OF SOME SET ALGORITHMS [J].

REINGOLD, EM .

JOURNAL OF THE ACM, 1972, 19 (04) :649-+

[8]

SNIR M, 1981, LNCS, V115, P305

[9] ON THE POLYHEDRAL DECISION PROBLEM [J].

YAO, AC ;

RIVEST, RL .

SIAM JOURNAL ON COMPUTING, 1980, 9 (02) :343-347

[10]

Yap C. K., 1978, 19th Annual Symposium on Foundations of Computer Science, P267, DOI 10.1109/SFCS.1978.25

← 1 →