Коммуникационная сложность для определения ассоциативности

12

Пусть { 0 , . , , , П - 1 } и : S × S S . Я хочу вычислить сложность коммуникации, решая, является ли ассоциативным.S=0,...,n1:S×SS

Модель следующая. задается в виде матрицы М . Алиса (соответственно Боб) получает половину записей матрицы случайным образом (то же самое для Боба). Я хочу вычислить количество записей в худшем случае, которые Алиса должна отправить Бобу, чтобы Боб мог принять решение об ассоциативности .M

На самом деле, это просто свести задачу о принятии решения о равенстве двух битовых строк размера к задаче принятия решения ассоциативности над S . Это означает, что сложность связи ассоциативности ограничена снизу Ω ( n ) . Тем не менее, я подозреваю, что этот LB не туго. Будучи определенным на входе размера n 2 , я бы предпочел найти сложность связи Ω ( n 2 ) .Ω(n)SΩ(n)n2Ω(n2)

Есть ли известный результат по этой проблеме? Ответ по очевидной причине, которую я не вижу?n2

Сильвен Пейроннет
источник
Не могли бы вы объяснить модель более подробно? Например, какие данные получают Алиса и Боб, и является ли это случайным или детерминированным (или квантовым)?
Робин Котари
Я отредактировал соответственно. Меня интересуют рандомизированные или детерминированные вещи (но не квантовые), даже если для меня важен практически только детерминированный каркас (я планирую использовать результат, чтобы доказать LB по размеру OBDD).
Сильвен Пейроннет
1
Я думаю, что это обычно называется односторонней связью, поскольку Бобу не разрешено отправлять биты Алисе в вашей модели.
Домоторп

Ответы:

10

nn2Snf(t)

Пер Вогсен
источник
1
Спасибо, я посмотрю на эту статью и вернусь сюда, чтобы сообщить вам.
Сильвен Пейроннет