DocumentCode
2892599
Title
Search problems in the decision tree model
Author
Lovász, László ; Naor, Moni ; Newman, Ilan ; Wigderson, Avi
Author_Institution
Eotvos Lorand Univ., Budapest, Hungary
fYear
1991
fDate
1-4 Oct 1991
Firstpage
576
Lastpage
585
Abstract
The relative power of determinism, randomness, and nondeterminism for search problems in the Boolean decision tree model is studied. It is shown that the CNF search problem is complete for all the variants of decision trees. It is then shown that the gaps between the nondeterministic, the randomized, and the deterministic complexities can be arbitrarily large for search problems. The special case of nondeterministic complexity is discussed
Keywords
Boolean algebra; computational complexity; decision theory; search problems; trees (mathematics); Boolean decision tree model; CNF search; complexities; determinism; nondeterminism; randomness; search problems; Boolean functions; Computational modeling; Decision trees; Electronic mail; Measurement standards; Polynomials; Probes; Search problems;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
Conference_Location
San Juan
Print_ISBN
0-8186-2445-0
Type
conf
DOI
10.1109/SFCS.1991.185422
Filename
185422
Link To Document