Помимо (детерминированной) сложности связи отношения , другой основной мерой для объема необходимой связи является номер раздела протокола . Связь между этими двумя показателями известна до постоянного фактора. Монография Кушилевица и Нисана (1997) даетR
Что касается второго неравенства, легко дать (бесконечное семейство) отношения с \ log_2 (pp (R)) = cc (R) .log 2 ( p p ( R ) ) = c c ( R )
Что касается первого неравенства, Doerr (1999) показал, что мы можем заменить фактор в первой оценке на . Насколько можно улучшить первую границу, если она вообще будет?
Дополнительная мотивация из-за сложности описания: Улучшение константы приведет к улучшению нижней границы минимального размера регулярных выражений, эквивалентных данному DFA, описывающему некоторый конечный язык, см. Gruber and Johannsen (2008).
Несмотря на то, не имеет прямого отношения к этому вопросу, Kushilevitz, Linial и Островского (1999) дал отношения с , где , является прямоугольник номер раздела .
РЕДАКТИРОВАТЬ: Заметьте, что вышеупомянутый вопрос эквивалентен следующему вопросу в сложности булевой схемы: Какая оптимальная константа такова, что каждая булева формула DeMorgan листового размера L может быть преобразована в эквивалентную формулу глубины не более ?
Рекомендации :
- Кушилевиц, Эяль; Нисан, Ноам: Сложность общения. Издательство Кембриджского университета, 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.
Ответы:
Итак, позвольте мне попытаться доказать, что два достаточно, то есть . Извините, но иногда я пишу листья вместо числа листьев / pp (R), всякий раз, когда число меньше 1, я, очевидно, имею в виду это. Кроме того, я обычно пишу <вместо чтобы улучшить читаемость не-tex.≤c c ( R ) ≤ 2 log2( р р ( р ) ) ≤
Косвенно предположим, что существует 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 листьев.
Во всех случаях мы сделали. Дайте мне знать, что вы думаете.
источник
Ссылки
Стасис Юкна. Сложность булевой функции: достижения и границы. Springer, 2012.
В.М. Храпченко. На связи между сложностью и глубиной. Методы Дискретного Анализа в Синтезе Систем Управления 32: 76–94, 1978.
источник