Randomized versus nondeterministic communication complexity

摘要

Our main result is the demonstration of a Boolean function f with nondeterministic and co-nondeterministic complexities O(log n) and ε-error randomized complexity &OHgr;(log2 n), for 0 ≤ ε 1/2. This is the first separation of this kind for a decision problem.