Search Problems in the Decision Tree Model (Preliminary Version)

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. >

Authors

• László Lovász 0001
• Moni Naor
• Ilan Newman
• Avi Wigderson

Keywords

• Search problems
• Decision trees
• Computational modeling
• Probes
• Boolean functions
• Measurement standards
• Polynomials
• Electronic mail
• Decision Tree
• Search Problem
• Lower Bound
• Princeton
• Point Distance
• Decision Problem
• Complex Communication
• Proof Of The Lemma
• Monomial
• Bottom Left Corner
• Exchange Networks
• Partial Match
• Pendent
• Call Detail Records
• Rest Of The Proof
• Induced Subgraph
• Path Points
• Input Bits