Misalkan Alice menerima himpunan bagian dan Bob menerima T ⊆ { 1 , ... , n } . Dijanjikan bahwa | S ∩ T | = 1 . Apa kompleksitas komunikasi acak untuk menentukan elemen umum S ∩ T ?
Ketertarikan saya pada ini adalah sebagai berikut. Biaya-komunikasi nol dari masalah ini adalah sejak Alice dan Bob hanya bisa menebak S ∩ T menggunakan koin publik dan batalkan jika mereka salah menebak. Namun, saya tidak bisa memikirkan protokol komunikasi biaya O ( log n ) . Karena tidak diketahui apakah biaya komunikasi nol jauh lebih rendah daripada biaya komunikasi acak, saya berpikir bahwa saya kehilangan sesuatu yang jelas di sini.
Biaya komunikasi nol didefinisikan sebagai berikut. Setelah Alice dan Bob menerima input mereka, mereka tidak boleh berkomunikasi sama sekali. Namun, mereka berbagi koin publik, dan mereka diizinkan untuk menjawab dengan "batalkan". Jika tidak dibatalkan pihak, mereka harus memberikan jawaban yang benar dengan probabilitas. Biaya nol komunikasi adalah log negatif dari kemungkinan tidak dibatalkan. Dalam arxiv: 1204.1505 ditunjukkan (antara lain) bahwa hampir semua batas bawah yang diketahui pada kompleksitas komunikasi sebenarnya batas bawah untuk nol-komunikasi.
Pembaruan: @Shitikanth menunjukkan bahwa kompleksitas komunikasi adalah . Jadi, ternyata ini memberikan celah antara biaya komunikasi dan biaya komunikasi nol. Tetapi arxiv: 1204.1505 tampaknya memberi kesan bahwa tidak ada celah seperti itu yang diketahui. Apa yang saya lewatkan?
sumber
Jawaban:
(Pengurangan dari set disjointness)
sumber
Saya harap ini membantu.
sumber
Protokol tercepat yang bisa saya pikirkan adalah bertukar alternatif sepasang elemen yang berdekatan secara acak, membuang hal-hal yang terlewati.
Alice [1,10,26,49,50] Bob [2,3,25,49,51]
Pasangan yang berdekatan dengan Alice adalah [10,26] sehingga Bob membuang 25
Alice [1,49,50] Bob [2,3,49,51]
Pasangan Bob yang berdekatan adalah [3,49] yang cocok dengan 49 sehingga berhenti
sumber