1.Previous
3.Next

are polynomially related. Blum and Impagliazzo, Hartmanis and Hemachandra, and Tardos independently discovered that . Noam Nisan found that the Monte Carlo randomized decision tree complexity is also polynomially related to deterministic decision tree complexity: . (Nisan also showed that .) A tighter relationship is known between the Monte Carlo and Las Vegas models: . This relationship is optimal up to polylogarithmic factors. As for quantum decision tree complexities, , and this bound is tight. Midrijanis

1.Previous
3.Next