Złożoność komunikacji przy podejmowaniu decyzji o powiązaniu

Niech { 0 , . . . , N - 1 }, a ∘ : S x S → S . Chcę obliczyć złożoność komunikacji przy podejmowaniu decyzji, czy ∘ jest skojarzone.$S=$$0,...,n-1$$\circ : S \times S \rightarrow S$$\circ$

Model jest następujący. podano jako matrycy M . Alice (lub. Bob) otrzymuje losowo połowę wpisów macierzy (to samo dla Boba). Chcę obliczyć najgorszy przypadek wpisów, które Alice musi wysłać do Boba, aby Bob mógł zdecydować o połączeniu ∘ .$\circ$$M$$\circ$

W rzeczywistości, można w prosty sposób zmniejszyć problem decydowania równości dwóch ciągów bitów o rozmiarze problemu zdecydowania się asocjatywności ∘ na S . Oznacza to, że złożoność komunikacyjna asocjatywności jest niższa niż Ω ( n ) . Podejrzewam jednak, że ten LB nie jest ciasny. Będąc zdefiniowanym na wejściu o wielkości n 2 , wolałbym znaleźć złożoność komunikacyjną Ω ( n 2 ) .$\Omega(n)$$\circ$$S$$\Omega(n)$$n^{2}$$\Omega(n^{2})$

Czy jest znany wynik tego problemu? Czy odpowiedź brzmi z oczywistego powodu, którego nie widzę?$n^{2}$

$n^{n^2}$$S$$n$$f(t)$