Пусть { 0 , . , , , П - 1 } и ∘ : S × S → S . Я хочу вычислить сложность коммуникации, решая, является ли ∘ ассоциативным.
Модель следующая. задается в виде матрицы М . Алиса (соответственно Боб) получает половину записей матрицы случайным образом (то же самое для Боба). Я хочу вычислить количество записей в худшем случае, которые Алиса должна отправить Бобу, чтобы Боб мог принять решение об ассоциативности ∘ .
На самом деле, это просто свести задачу о принятии решения о равенстве двух битовых строк размера к задаче принятия решения ассоциативности ∘ над S . Это означает, что сложность связи ассоциативности ограничена снизу Ω ( n ) . Тем не менее, я подозреваю, что этот LB не туго. Будучи определенным на входе размера n 2 , я бы предпочел найти сложность связи Ω ( n 2 ) .
Есть ли известный результат по этой проблеме? Ответ по очевидной причине, которую я не вижу?
источник
Ответы:
источник