EXPONENTIAL LOWER BOUNDS FOR SOME NP-COMPLETE PROBLEMS IN A RESTRICTED LINEAR DECISION TREE MODEL

被引：4

作者：

UKKONEN, E

机构：

来源：

BIT | 1983年 / 23卷 / 02期

关键词：

D O I：

10.1007/BF02218439

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

引用

页码：181 / 192

页数：12

共 9 条

DOBKIN, D ;

LIPTON, RJ .

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

DOBKIN, DP ;

LIPTON, RJ .

[3]

Garey Michael R., 1979, COMPUTERS INTRACTABI

[4]

Karp R.M., 1972, COMPLEXITY COMPUTER

[5]

Rabin M. O., 1972, Journal of Computer and System Sciences, V6, P639, DOI 10.1016/S0022-0000(72)80034-5

[6]

REINGOLD EM, 1971, 12TH P IEEE S SWITCH, P216

[7]

SNIR M, 1981, SPRINGER LECTURE NOT, V115, P305

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

YAO, AC ;

RIVEST, RL .

[9]

YAO AC, 1981, 13TH ANN ACM S THEOR, P123