SEARCH PROBLEMS IN THE DECISION TREE MODEL

被引：32

作者：

LOVASZ, L

NAOR, M

NEWMAN, I

WIGDERSON, A

机构：

[1] EOTVOS LORAND UNIV, BUDAPEST, HUNGARY

[2] WEIZMANN INST SCI, DEPT APPL MATH, IL-76100 REHOVOT, ISRAEL

[3] RUTGERS STATE UNIV, CTR DISCRETE MATH & THEORET COMP SCI, NEW BRUNSWICK, NJ 08903 USA

[4] HEBREW UNIV JERUSALEM, DEPT COMP SCI, IL-91904 JERUSALEM, ISRAEL

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1995年 / 8卷 / 01期

关键词：

BOOLEAN FUNCTIONS; DECISION TREES;

D O I：

10.1137/S0895480192233867

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The relative power of determinism, randomness, and nondeterminism for search problems in the Boolean decision tree model is studied. It is shown that the gaps between the nondeterministic, the randomized, and the deterministic complexities can be arbitrarily large for search problems. An interesting connection of this model to the complexity of resolution proofs is also mentioned.

引用

页码：119 / 132

页数：14

共 21 条

[1]

Babai L., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P337, DOI 10.1109/SFCS.1986.15

[2]

BLAKE A, 1937, THESIS CHICAGO U CHI

[3]

Blum M., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P118, DOI 10.1109/SFCS.1987.30

[4] MANY HARD EXAMPLES FOR RESOLUTION [J].

CHVATAL, V ;

SZEMEREDI, E .

JOURNAL OF THE ACM, 1988, 35 (04) :759-768

[5]

DAVIS M, 1960, J ACM, V7, P210

[6]

HARTMANIS J, 1987, 2ND P STRUCT COMPL T, P160

[7]

Hirsch M. D., 1989, Journal of Complexity, V5, P379, DOI 10.1016/0885-064X(89)90017-4

[8]

IMPAGLIAZZO R, 1988, 3RD STRUCT COMPL THE, P29

[9]

IRANI S, 1990, ANN IEEE SYMP FOUND, P470

[10]

KARCHMER M, 1988, 20TH P ANN ACM S THE, P539

← 1 2 3 →