Номер раздела протокола и детерминированная сложность связи

22

Помимо (детерминированной) сложности связи отношения , другой основной мерой для объема необходимой связи является номер раздела протокола . Связь между этими двумя показателями известна до постоянного фактора. Монография Кушилевица и Нисана (1997) даетRсс(р)р пп(р)

сс(р)/3журнал2(пп(р))сс(р),

Что касается второго неравенства, легко дать (бесконечное семейство) отношения с \ log_2 (pp (R)) = cc (R) .log 2 ( p p ( R ) ) = c c ( R )ржурнал2(пп(р))знак равносс(р)

Что касается первого неравенства, Doerr (1999) показал, что мы можем заменить фактор сзнак равно3 в первой оценке на сзнак равно2,223 . Насколько можно улучшить первую границу, если она вообще будет?

Дополнительная мотивация из-за сложности описания: Улучшение константы 2,223 приведет к улучшению нижней границы минимального размера регулярных выражений, эквивалентных данному DFA, описывающему некоторый конечный язык, см. Gruber and Johannsen (2008).

Несмотря на то, не имеет прямого отношения к этому вопросу, Kushilevitz, Linial и Островского (1999) дал отношения р с сс(р)/(2-о(1))журнал2(рп(р)) , где рп(р) , является прямоугольник номер раздела .

РЕДАКТИРОВАТЬ: Заметьте, что вышеупомянутый вопрос эквивалентен следующему вопросу в сложности булевой схемы: Какая оптимальная константа с такова, что каждая булева формула DeMorgan листового размера L может быть преобразована в эквивалентную формулу глубины не более сжурнал2L ?

Рекомендации :

  • Кушилевиц, Эяль; Нисан, Ноам: Сложность общения. Издательство Кембриджского университета, 1997.
  • Кушилевиц, Эяль; Линиал, Натан; Островский, Рафаил: Гипотеза о линейной матрице в сложности коммуникации неверна, Combinatorica 19 (2): 241-254, 1999.
  • Doerr, Benjamin: сложность связи и номер раздела протокола, Технический отчет 99-28, Berichtsreihe des Mathematischen Seminars der Universität Kiel, 1999.
  • Грубер, Герман; Йоханнсен, Ян: оптимальные нижние границы для размера регулярных выражений с использованием сложности связи. В кн .: Основы программных наук и вычислительных структур 2008 (FoSSaCS 2008), LNCS 4962, 273-286. Springer.
Герман Грубер
источник
Я не знал о второй ссылке, и я попытался найти ее в Google, но не нашел онлайн-версию. У вас есть ссылка?
Маркос Вильягра
это домашняя страница автора? mpi-inf.mpg.de/~doerr
Маркос Вильягра
Да, это домашняя страница автора. Ссылка на citeseerX, которую я использовал для загрузки статьи, похоже, исчезла. Вы можете спросить в своей библиотеке, могут ли они получить бумажную копию; но может быть лучше спросить автора, готов ли он разместить его на своей домашней странице или в архиве.
Герман Грубер
2
Единственное, что мне может пригодиться в последнее время, это статья lab2.kuis.kyoto-u.ac.jp/~kenya/MFCS2010.pdf .
Хартмут Клаук
2
Я действительно не понимаю, за что вы предлагаете награду. Вы хотите меньшую константу вместо 3? Вы цитируете бумагу Doerr там, где она улучшена до 2,223 ...
Domotorp

Ответы:

10

Итак, позвольте мне попытаться доказать, что два достаточно, то есть . Извините, но иногда я пишу листья вместо числа листьев / pp (R), всякий раз, когда число меньше 1, я, очевидно, имею в виду это. Кроме того, я обычно пишу <вместо чтобы улучшить читаемость не-tex.сс(р)2журнал2(пп(р))

Косвенно предположим, что существует R, для которого это не так, и возьмем R с наименьшим возможным pp (R), что нарушает неравенство. В основном мы должны показать, что, используя два бита, мы можем вдвое сократить число листьев во всех четырех исходах дерева протокола, тогда мы закончили с использованием индукции.

Обозначим возможный набор входных данных Алисы через X и Боба через Y. Возьмем центр дерева протоколов, который достигает листьев pp (R), т.е. удаляем узел, дерево которого распадается на три части, каждая из которых имеет не более 1/2 из pp (R) уходит, и обозначим соответствующие входы через X0 и Y0. Без ограничения общности мы можем предположить, что Алиса говорит в центре, и она говорит, принадлежит ли ее вход XL или XR, чье несвязанное объединение X0. Обозначим отношение листьев к pp (R) в XL Y0 через L, в XR × Y0 через R, а в остальных - через D. Теперь мы разделим остальное на еще три части, аналогично Doerr, обозначая листья, прямоугольник которых пересекают Y0 × X по A, прямоугольник которого пересекает X0 × Y по B, а остальные по C. Обратите внимание, что A + B + C = D.××××

Теперь мы знаем, что L + R> 1/2, L, R <1/2 и без ограничения общности можем предположить, что L не больше R. Мы также знаем D = A + B + C <1/2. Отсюда следует, что 2L + A + B <1, откуда мы знаем, что либо L + A <1/2, либо L + B <1/2, это будут два наших случая.

Случай L + A <1/2: Сначала Боб сообщает, принадлежит ли его вход Y0 или нет. Если нет, у нас осталось не более D <1/2 листьев. Если это так, то Алиса сообщает, принадлежит ли ее ввод XR или нет. Если нет, то у нас осталось не более L + A <1/2 листьев. Если это так, то у нас остается R <1/2 листьев.

Случай L + B <1/2: Первая Алиса сообщает, принадлежит ли ее ввод XR или нет. Если это так, то Боб сообщает, принадлежит ли он к Y0 или нет, в зависимости от этого у нас остается R или B. Если ввод Алисы не в XR, то Алиса сообщает, находится ли ее ввод в XL или нет. Если это так, то у нас осталось L + B <1/2 листьев. Если нет, то у нас осталось не более D <1/2 листьев.

Во всех случаях мы сделали. Дайте мне знать, что вы думаете.

domotorp
источник
1
2L+A+В1L+р+A+В+Сзнак равно1С0Lр
3

с2с1,73

Ссылки

Стасис Юкна. Сложность булевой функции: достижения и границы. Springer, 2012.

В.М. Храпченко. На связи между сложностью и глубиной. Методы Дискретного Анализа в Синтезе Систем Управления 32: 76–94, 1978.

Герман Грубер
источник
1
Эта глава посвящена формулам, а не сложности общения, но доказательства действительно похожи. Эти проблемы эквивалентны?
Домоторп
Да, эти проблемы эквивалентны. Доказательство - игры Карчмера-Вигдерсона. См., Например, теорему 3.13 в книге Юкны. (Обратите внимание, что эквивалентность имеет место для формул Деморгана, а не для общих булевых формул по полному базису.)
Герман Грубер
В играх KW цель состоит в том, чтобы найти другую координату, если обещание состоит в том, что f (x) отличается от f (y), так что это сильно отличается от сложности коммуникации в целом.
Домоторп