Each of two players independently chooses one subset of a given finite set with n elements. How many bits of information must be communicated between the two players until at least one of them knows whether they have exactly t elements in common. Tamm has shown that the trivial protocol is (up to one bit) optimal for deterministic communication of t-intersection. The authors show that also non-deterministic communication has the same order of complexity.
展开▼
