Misalkan { 0 , . . . , N - 1 } dan ∘ : S × S → S . Saya ingin menghitung kompleksitas komunikasi untuk memutuskan apakah ∘ asosiatif.
Modelnya adalah sebagai berikut. diberikan sebagai matriks M . Alice (resp. Bob) diberikan setengah dari entri matriks secara acak (sama untuk Bob). Saya ingin menghitung jumlah entri terburuk yang harus dikirim Alice kepada Bob sehingga Bob dapat memutuskan asosiatifitas ∘ .
Bahkan, itu adalah sederhana untuk mengurangi masalah memutuskan kesamaan dua string bit ukuran untuk masalah memutuskan associativity dari ∘ lebih S . Ini berarti bahwa kompleksitas komunikasi dari associativity lebih rendah dibatasi oleh Ω ( n ) . Namun, saya curiga bahwa LB ini tidak ketat. Didefinisikan pada input ukuran n 2 , saya lebih suka menemukan kompleksitas komunikasi Ω ( n 2 ) .
Apakah ada hasil yang diketahui tentang masalah ini? Apakah jawabannya adalah untuk alasan yang jelas saya tidak melihat?
sumber
Jawaban:
sumber