kompleksitas komunikasi multi-partai dari "Set Partition problem"

Dalam suatu aplikasi yang saya pertimbangkan, saya perlu mengetahui kompleksitas komunikasi dari masalah berikut:

Diberikan , misalkan S adalah himpunan bilangan bulat dari 1 ke n . Alice, Bob, dan Carol masing-masing menerima subset S , dilambangkan oleh A , B , dan C , masing-masing. Mereka ingin memeriksa apakah A , B dan C membentuk partisi dari S , yaitu, mereka menguraikan dan serikat mereka adalah S .$n$$S$$1$$n$$S$$A$$B$$C$$A$$B$$C$$S$$S$

Saya sangat tertarik dengan kasus 3 pihak tetapi kasus-kasus lain juga akan menarik. Perhatikan bahwa untuk kasus 2 pihak, masalahnya setara dengan masalah EQUALITY sehingga memiliki batas bawah untuk protokol deterministik tetapi O ( log n ) batas atas untuk protokol acak.$\Omega(n)$$O(\log n)$

Pertanyaan saya adalah apakah masalah ini diketahui sebelumnya. Jika Anda tahu ada masalah yang mungkin terkait, saya akan tertarik untuk mengetahuinya juga.

Batas bawah linier pada CC deterministik mengikuti dengan menetapkan salah satu set menjadi kosong.

Untuk acak logaritmik atas terikat, catatan pertama bahwa masalah ini dapat dikurangi dengan masalah menanyakan apakah jumlah dari tiga $3n$ -bit nomor adalah persis $2^{3n}-1$ . Yang ini dapat diselesaikan dalam $O(\log n)$ komunikasi acak oleh para pemain yang mengoperasikan mod $O(\log n)$ acak ( log n ) -bit prime.

Saya mencari pertanyaan yang sedikit berbeda, yang sepertinya terkait. Apa yang akan menjadi referensi yang baik untuk perincian tentang batas atas acak dalam jawaban di atas?