Оценки на полудуплексную коммуникационную сложность и задача о топологическом вложении раскрашенных деревьев
|
Введение 3
1 Определения 7
1.1 Формулы Де Моргана 7
1.2 Коммуникационные протоколы 8
1.3 Связь протоколов и формул 9
1.4 Двухцветные деревья 10
1.5 Полудуплексные модели 11
2 Известные результаты 13
3 Постановка задачи про универсальные формулы 15
4 Сложность 15
5 Задача о раскрашенных деревьях 21
5.1 Верхние оценки 21
5.2 Нижняя оценка 24
6 Задача о вложении формул 27
7 Практические результаты 33
8 Read-once вложение и вложение термов 34
8.1 Read-once вложение 34
8.2 Вложение в общем случае 35
8.3 Применение на практике 37
9 Универсальные формулы над полным базисом 39
10 Оценки на коммуникационную сложность 41
Заключение 44
Список литературы
1 Определения 7
1.1 Формулы Де Моргана 7
1.2 Коммуникационные протоколы 8
1.3 Связь протоколов и формул 9
1.4 Двухцветные деревья 10
1.5 Полудуплексные модели 11
2 Известные результаты 13
3 Постановка задачи про универсальные формулы 15
4 Сложность 15
5 Задача о раскрашенных деревьях 21
5.1 Верхние оценки 21
5.2 Нижняя оценка 24
6 Задача о вложении формул 27
7 Практические результаты 33
8 Read-once вложение и вложение термов 34
8.1 Read-once вложение 34
8.2 Вложение в общем случае 35
8.3 Применение на практике 37
9 Универсальные формулы над полным базисом 39
10 Оценки на коммуникационную сложность 41
Заключение 44
Список литературы
Определение 1. Формула Де Моргана от переменных x1,... ,xn— это двоичное дерево, где каждый лист помечен литералом{x1,..., xn,— x1,..., — xn} или константой {0,1}, и каждая внутренняя вершина помечена логической связкой Л или У.
Будем говорить, что формула ф вычисляет булеву функцию f: {0,1}n^ {0,1}, если для любого x G {0,1}nзначение ф на входе x совпадает с f (x). Размером формулы ф называется количество листьев, а глубиной формулы ф — высота дерева, т.е. количество рёбер в самом длинном простом пути от корня до некоторого листа.
Определение 2. Формульной сложностью L(f) функции f называется минимальная функция s, такая что f от n переменных вычисляется формулами Де Моргана размера s(n).
Определение 3. Формульной глубиной D(f) функции f называется минимальная функция d, такая что f от n переменных вычисляется формулами Де Моргана глубины d(n).
Эти два показателя эквивалентны с точностью до логарифмирования и умножения на константу (log2L(f)
В работе [7] Карчмером и Вигдерсоном было замечено, что формулы в базисе Де Моргана тесно связаны с задачами коммуникационной сложности. Коммуникационная сложность — это мощный инструмент с приложениями в алгоритмах, схемной сложности, сложности доказательств и многих других областях теоретической информатики. В классической модели коммуникационной сложности, введенной Яо в 1979 году [19], два игрока, Алиса и Боб, пытаются вычислить f (x,y)для некоторой функции f, где Алиса знает только x, а Боб знает только у. Игроки могут общаться, отправляя друг другу битовые сообщения, по одному биту за раунд. В конце общения оба игрока должны знать значение f (x,y). В частности, эта взаимосвязь, установленная в работе [7], позволяет получать оценки на формульную сложность и формульную глубину булевых функций через доказательство оценок на размер и глубину коммуникационных протоколов. В дальнейшем в работе [6] была сформулирована гипотеза Карчмера — Раза — Вигдерсона.
Определение 4. Пусть f: {0,1}n^ {0,1}, д : {0,1}m^ {0,1} булевы функции. Композиция f c g : ({0,1}m)n^ {0,1} определяется равенством
fc g(xi,...,Xn) = f (g(xi),...,g(x„)).
Гипотеза 1 (KRW Гипотеза). D(fcg)« D(f )+D(g). Или в терминах формульной сложности: L(f c д') « L(f) • L(g)
Доказательство этой гипотезы напрямую влечет суперполиномиальную нижнюю оценку на формульную сложность явной функции из класса P и, как следствие, разделение классов сложности P и NC1. Для того, чтобы это понять, рассмотрим функцию F: {0,1}2N^ {0,1}, которая принимает на вход таблицу истинности некоторой функции f : {0,1}logN^ {0,1} и строку x G{0,1}N, а на выход выдает F (f, x) = (f c • • • c f )(x), где композиция берется log N/ log log Nраз. Если гипотеза верна, то D(F) ^ log2N/ log log N, так как можно рассмотреть функцию f сложности ^ log N. Отсюда получаем супер-логарифмическую нижнюю оценку на формульную глубину функции F :
log N log2N
D(F) = D(f c^c f) « °^— D(f) « og—- = w(log N).
7 log log N log log N
Дальнейшие исследования с целью доказательства KRW-гитпотезы и некоторых ее ослабленных вариантов велись в работах [10,3,17,18]. Мы же в этой работе пытаемся разрешить некоторые трудности, которые возникают в плане доказательства суперполиномиальной нижней оценки на размер формул.
Более конкретно, один из подходов (см. [10]) состоит в том, чтобы доказать нижнюю оценку на коммуникационную сложность композиции произвольной булевой функции с функцией мультиплексор MUX, которая получает на вход таблицу истинности и вход некоторой булевой функции, и выдает значение этой функции на этом входе: MUX(f, x) = f (x). Если предположить, что нижняя оценка доказана, то мы хотим предъявить такую сложную для мультиплексора функцию f. Предположим, что такой функции не существует, то есть для каждой конкретной функции MUX(f, •) вычисляется за маленькое число раундов коммуникации. Давайте тогда построим протокол, который будет вычислять MUX для любой функции, и при этом использовать малое число битов. Одна из идей, как это можно было бы сделать, состоит в том, что игроки, получив на вход функцию f и входы для нее, выберут оптимальный протокол для этой функции и будут ему следовать. Так, получится противоречие с тем, что коммуникационная сложность MUX не выше, чем у самой сложной функции f , которая может быть в него подставлена. Однако в классической коммуникационной модели игроки не могут в зависимости от входа выбирать протокол, по которому они будут действовать. Эту проблему можно обойти несколькими способами.
• Зафиксировать очередность ходов: игроки ходят строго по-очереди, начиная с Алисы. Но в таком случае сложность коммуникации может увеличится в 2 раза по сравнению с классической, и поэтому нижнюю оценку нужно будет делать больше в 2 раза, по сравнению с потенциальной (подробнее в работе [10]).
• Найти универсальный протокол с фиксированной структурой глубины меньше чем 2d, который сможет решить отношение Карчмера — Вигдерсона для любой функции, коммуникационная сложность которой не больше d.Тогда у нас, опять же, сложность коммуникации увеличится, но в меньшее число раз, что даст возможность в будущем доказать более простую нижнюю оценку.
• И третий способ — рассмотреть полудуплексные модели, где игрокам разрешено говорить одновременно.
Остановимся подробнее на последних двух пунктах. В статье [4] авторы предложили рассмотреть модель коммуникации, где игроки говорят по полудуплексному каналу. Известным примером полудуплексной связи является разговор по рации: один собеседник должен удерживать кнопку, чтобы передавать сообщение, а другой должен удерживать ее не нажатой, чтобы это сообщение получить. Если два человека пытаются говорить одновременно, то они не слышат друг друга. Формально говоря, в каждом раунде каждый игрок выбирает одно из трех действий: отправить 0, отправить 1 или слушать. Существует три разных типа раундов: классический раунд, когда один игрок отправляет какой-то бит, а другой получает, потерянный раунд, когда оба игрока отправляют битовые сообщения (эти биты теряются), и тихий раунд, когда оба игрока слушают. В работе [4] авторы определили три варианта полудуплексной модели на основе того, что происходит в тихих раундах: полудуплексные модели с тишиной, с нулем и с противником (дополнительную информацию см. в разделе 1.5). Оказалось, что сложность связи в полудуплексных моделях не только отличается от классического случая, но и ведет себя иначе. Например, в классическом случае функция равенства, функция дизъюнктности и функция скалярного произведения имеют сложность n+ 1, что означает, что все три функции являются самыми сложными в этой модели. В полудуплексных моделях с тишиной и с нулем эти три функции имеют различную сложность, в обоих случаях меньшую, чем в классической модели. В работе [11] результаты сложности полудуплексной связи использовались для доказательства нижней оценки композиции универсального отношения с игрой Карчмера — Вигдерсона для некоторой функции. Авторы предполагают, что лучшее понимание сложности полудуплексной коммуникации может помочь достичь новых продвижений в изучении гипотезы KRW, и даже доказать суперкубическую нижнюю оценку на размер формулы Де Моргана для явной функции.
Мы продолжаем исследование, начатое в статье [4], и закрываем некоторые открытые вопросы, сформулированные там и касающиеся сложности популярных функций в полудуплексных моделях коммуникационной сложности. Кроме того, мы исследуем некоторые вопросы, связанные с формульной сложностью булевых функций в базисе Де Моргана, с точки зрения классической коммуникационной сложности [19]. Для лучшего понимания свойств коммуникации мы задаемся следующим вопросом: существуют ли классический коммуникационный протокол, который может быть использован для решения множества различных задач?
Изучается следующая модификация коммуникационной задачи: Алиса и Боб договорились о протоколе заранее, до получения задачи, то есть они фиксировали всю структуру протокола, кроме пометок на листьях. Сколько различных задач сможет решить такой протокол, если в зависимости от полученной задачи мы можем менять только ответы, которые написаны в листьях? Более конкретно, нас будет интересовать следующий вопрос: при каких условиях существует универсальный протокол, решающий все задачи, для которых CC(R)
Одним из наших подходов к этой проблеме является изучение частного случая вложения формул, а именно, вложения двухцветных деревьев. Мы доказываем нижнюю оценку на коэффициент вложения и приводим наши алгоритмические результаты для вычисления верхней оценки. Помимо этого мы доказываем, что в общем случае задача проверки вложения для двух заданных формул является Ефполной, и приводим другие теоретические результаты, которые могут помочь в дальнейшем исследовании.
Изначально задача об универсальных коммуникационных протоколах была сформулирована Расселом Импальяццо и частично решена Аароном Потехиным, результаты которого мы приводим в разделе 2. Насколько нам известно, других исследований по этой теме не было, и задача об универсальных протоколах никем фундаментально не изучалась. В процессе изучения стало понятно, что эту задачу можно при некоторых условиях свести к чисто комбинаторной - вложению друг в друга двухцветных деревьев. Дополнительно, эта задача интересна тем, что тут можно применить методы компьютерного перебора для таких объектов как двухцветные деревья и булевы формулы над базисом Де Моргана.
Стоит также отметить, что задача поиска универсальных формул (частный случай схем), которые могут моделировать все формулы ограниченной глубины, имеет прикладную мотивацию в области разработки плат, ведь для схем контактов на плате важно иметь как можно большую функциональность, то есть иметь возможность вычислять как можно больше различных функций от своих компонентов.
Структура работы.
В секции 1 вводятся основные определения и теоремы, которые будут использоваться в дальнейшем. В разделе 2 приводится обзор известных результатов для универсальных булевых формул. В разделе 3 подробно формулируется задача об универсальных формулах в базисе Де Моргана. В секции 4 доказывается сложность задачи проверки вложения для пары формул. В секции 5 исследуется задача о раскрашенных деревьях и доказываются нижние оценки для топологических вложений. В секции 6 техника из предыдущих глав применяется к задаче про вложение формул, и доказываются некоторые теоретические результаты, которые могут помочь в практическом исследовании. В главе 8 описывается новая идея для вложения формул и приводятся некоторые результаты по этому поводу. В секции 9 рассматривается задача о вложении формул над полным булевым базисом B2,доказывается верхняя оценка на глубину универсальной структуры. В секции 10 доказываются оценки на сложность функций в полудуплексных моделях, а также приводятся некоторые оценки для классической коммуникационной модели.
Будем говорить, что формула ф вычисляет булеву функцию f: {0,1}n^ {0,1}, если для любого x G {0,1}nзначение ф на входе x совпадает с f (x). Размером формулы ф называется количество листьев, а глубиной формулы ф — высота дерева, т.е. количество рёбер в самом длинном простом пути от корня до некоторого листа.
Определение 2. Формульной сложностью L(f) функции f называется минимальная функция s, такая что f от n переменных вычисляется формулами Де Моргана размера s(n).
Определение 3. Формульной глубиной D(f) функции f называется минимальная функция d, такая что f от n переменных вычисляется формулами Де Моргана глубины d(n).
Эти два показателя эквивалентны с точностью до логарифмирования и умножения на константу (log2L(f)
В работе [7] Карчмером и Вигдерсоном было замечено, что формулы в базисе Де Моргана тесно связаны с задачами коммуникационной сложности. Коммуникационная сложность — это мощный инструмент с приложениями в алгоритмах, схемной сложности, сложности доказательств и многих других областях теоретической информатики. В классической модели коммуникационной сложности, введенной Яо в 1979 году [19], два игрока, Алиса и Боб, пытаются вычислить f (x,y)для некоторой функции f, где Алиса знает только x, а Боб знает только у. Игроки могут общаться, отправляя друг другу битовые сообщения, по одному биту за раунд. В конце общения оба игрока должны знать значение f (x,y). В частности, эта взаимосвязь, установленная в работе [7], позволяет получать оценки на формульную сложность и формульную глубину булевых функций через доказательство оценок на размер и глубину коммуникационных протоколов. В дальнейшем в работе [6] была сформулирована гипотеза Карчмера — Раза — Вигдерсона.
Определение 4. Пусть f: {0,1}n^ {0,1}, д : {0,1}m^ {0,1} булевы функции. Композиция f c g : ({0,1}m)n^ {0,1} определяется равенством
fc g(xi,...,Xn) = f (g(xi),...,g(x„)).
Гипотеза 1 (KRW Гипотеза). D(fcg)« D(f )+D(g). Или в терминах формульной сложности: L(f c д') « L(f) • L(g)
Доказательство этой гипотезы напрямую влечет суперполиномиальную нижнюю оценку на формульную сложность явной функции из класса P и, как следствие, разделение классов сложности P и NC1. Для того, чтобы это понять, рассмотрим функцию F: {0,1}2N^ {0,1}, которая принимает на вход таблицу истинности некоторой функции f : {0,1}logN^ {0,1} и строку x G{0,1}N, а на выход выдает F (f, x) = (f c • • • c f )(x), где композиция берется log N/ log log Nраз. Если гипотеза верна, то D(F) ^ log2N/ log log N, так как можно рассмотреть функцию f сложности ^ log N. Отсюда получаем супер-логарифмическую нижнюю оценку на формульную глубину функции F :
log N log2N
D(F) = D(f c^c f) « °^— D(f) « og—- = w(log N).
7 log log N log log N
Дальнейшие исследования с целью доказательства KRW-гитпотезы и некоторых ее ослабленных вариантов велись в работах [10,3,17,18]. Мы же в этой работе пытаемся разрешить некоторые трудности, которые возникают в плане доказательства суперполиномиальной нижней оценки на размер формул.
Более конкретно, один из подходов (см. [10]) состоит в том, чтобы доказать нижнюю оценку на коммуникационную сложность композиции произвольной булевой функции с функцией мультиплексор MUX, которая получает на вход таблицу истинности и вход некоторой булевой функции, и выдает значение этой функции на этом входе: MUX(f, x) = f (x). Если предположить, что нижняя оценка доказана, то мы хотим предъявить такую сложную для мультиплексора функцию f. Предположим, что такой функции не существует, то есть для каждой конкретной функции MUX(f, •) вычисляется за маленькое число раундов коммуникации. Давайте тогда построим протокол, который будет вычислять MUX для любой функции, и при этом использовать малое число битов. Одна из идей, как это можно было бы сделать, состоит в том, что игроки, получив на вход функцию f и входы для нее, выберут оптимальный протокол для этой функции и будут ему следовать. Так, получится противоречие с тем, что коммуникационная сложность MUX не выше, чем у самой сложной функции f , которая может быть в него подставлена. Однако в классической коммуникационной модели игроки не могут в зависимости от входа выбирать протокол, по которому они будут действовать. Эту проблему можно обойти несколькими способами.
• Зафиксировать очередность ходов: игроки ходят строго по-очереди, начиная с Алисы. Но в таком случае сложность коммуникации может увеличится в 2 раза по сравнению с классической, и поэтому нижнюю оценку нужно будет делать больше в 2 раза, по сравнению с потенциальной (подробнее в работе [10]).
• Найти универсальный протокол с фиксированной структурой глубины меньше чем 2d, который сможет решить отношение Карчмера — Вигдерсона для любой функции, коммуникационная сложность которой не больше d.Тогда у нас, опять же, сложность коммуникации увеличится, но в меньшее число раз, что даст возможность в будущем доказать более простую нижнюю оценку.
• И третий способ — рассмотреть полудуплексные модели, где игрокам разрешено говорить одновременно.
Остановимся подробнее на последних двух пунктах. В статье [4] авторы предложили рассмотреть модель коммуникации, где игроки говорят по полудуплексному каналу. Известным примером полудуплексной связи является разговор по рации: один собеседник должен удерживать кнопку, чтобы передавать сообщение, а другой должен удерживать ее не нажатой, чтобы это сообщение получить. Если два человека пытаются говорить одновременно, то они не слышат друг друга. Формально говоря, в каждом раунде каждый игрок выбирает одно из трех действий: отправить 0, отправить 1 или слушать. Существует три разных типа раундов: классический раунд, когда один игрок отправляет какой-то бит, а другой получает, потерянный раунд, когда оба игрока отправляют битовые сообщения (эти биты теряются), и тихий раунд, когда оба игрока слушают. В работе [4] авторы определили три варианта полудуплексной модели на основе того, что происходит в тихих раундах: полудуплексные модели с тишиной, с нулем и с противником (дополнительную информацию см. в разделе 1.5). Оказалось, что сложность связи в полудуплексных моделях не только отличается от классического случая, но и ведет себя иначе. Например, в классическом случае функция равенства, функция дизъюнктности и функция скалярного произведения имеют сложность n+ 1, что означает, что все три функции являются самыми сложными в этой модели. В полудуплексных моделях с тишиной и с нулем эти три функции имеют различную сложность, в обоих случаях меньшую, чем в классической модели. В работе [11] результаты сложности полудуплексной связи использовались для доказательства нижней оценки композиции универсального отношения с игрой Карчмера — Вигдерсона для некоторой функции. Авторы предполагают, что лучшее понимание сложности полудуплексной коммуникации может помочь достичь новых продвижений в изучении гипотезы KRW, и даже доказать суперкубическую нижнюю оценку на размер формулы Де Моргана для явной функции.
Мы продолжаем исследование, начатое в статье [4], и закрываем некоторые открытые вопросы, сформулированные там и касающиеся сложности популярных функций в полудуплексных моделях коммуникационной сложности. Кроме того, мы исследуем некоторые вопросы, связанные с формульной сложностью булевых функций в базисе Де Моргана, с точки зрения классической коммуникационной сложности [19]. Для лучшего понимания свойств коммуникации мы задаемся следующим вопросом: существуют ли классический коммуникационный протокол, который может быть использован для решения множества различных задач?
Изучается следующая модификация коммуникационной задачи: Алиса и Боб договорились о протоколе заранее, до получения задачи, то есть они фиксировали всю структуру протокола, кроме пометок на листьях. Сколько различных задач сможет решить такой протокол, если в зависимости от полученной задачи мы можем менять только ответы, которые написаны в листьях? Более конкретно, нас будет интересовать следующий вопрос: при каких условиях существует универсальный протокол, решающий все задачи, для которых CC(R)
Одним из наших подходов к этой проблеме является изучение частного случая вложения формул, а именно, вложения двухцветных деревьев. Мы доказываем нижнюю оценку на коэффициент вложения и приводим наши алгоритмические результаты для вычисления верхней оценки. Помимо этого мы доказываем, что в общем случае задача проверки вложения для двух заданных формул является Ефполной, и приводим другие теоретические результаты, которые могут помочь в дальнейшем исследовании.
Изначально задача об универсальных коммуникационных протоколах была сформулирована Расселом Импальяццо и частично решена Аароном Потехиным, результаты которого мы приводим в разделе 2. Насколько нам известно, других исследований по этой теме не было, и задача об универсальных протоколах никем фундаментально не изучалась. В процессе изучения стало понятно, что эту задачу можно при некоторых условиях свести к чисто комбинаторной - вложению друг в друга двухцветных деревьев. Дополнительно, эта задача интересна тем, что тут можно применить методы компьютерного перебора для таких объектов как двухцветные деревья и булевы формулы над базисом Де Моргана.
Стоит также отметить, что задача поиска универсальных формул (частный случай схем), которые могут моделировать все формулы ограниченной глубины, имеет прикладную мотивацию в области разработки плат, ведь для схем контактов на плате важно иметь как можно большую функциональность, то есть иметь возможность вычислять как можно больше различных функций от своих компонентов.
Структура работы.
В секции 1 вводятся основные определения и теоремы, которые будут использоваться в дальнейшем. В разделе 2 приводится обзор известных результатов для универсальных булевых формул. В разделе 3 подробно формулируется задача об универсальных формулах в базисе Де Моргана. В секции 4 доказывается сложность задачи проверки вложения для пары формул. В секции 5 исследуется задача о раскрашенных деревьях и доказываются нижние оценки для топологических вложений. В секции 6 техника из предыдущих глав применяется к задаче про вложение формул, и доказываются некоторые теоретические результаты, которые могут помочь в практическом исследовании. В главе 8 описывается новая идея для вложения формул и приводятся некоторые результаты по этому поводу. В секции 9 рассматривается задача о вложении формул над полным булевым базисом B2,доказывается верхняя оценка на глубину универсальной структуры. В секции 10 доказываются оценки на сложность функций в полудуплексных моделях, а также приводятся некоторые оценки для классической коммуникационной модели.
В рамках этой работы были достигнуты следующие результаты:
• Доказана Е^ полнота задачи проверки вложения для двух заданных формул над базисом Де Моргана.
• Получены верхние и нижние оценки на топологическое вложение деревьев для различных значений параметров nи к.
• Доказана теорема про сведение вложения в общем случае к топологическому вложению раскрашенных деревьев.
• Доказана характеризация read-once вложения через вложение минтермов и макстермов, и ее обобщение на вложение в общем случае.
• Доказаны оценки на сложность функций Parity и MODpв классической коммуникационной модели и в полудуплексной модели с тишиной.
• Проведено исследование с целью поиска универсальных формул для малых глубин методами компьютерного анализа.
Часть результатов, связанная с оценками на сложность функций в полудуплексных моделях коммуникационной сложности, была опубликована в статье [13], часть про универсальные коммуникационные протоколы готовится к публикации.
Все еще остается открытым вопрос о точной оценке на коэффициент топологического вложения у, а также о какой-нибудь нетривиальной нижней оценке на универсальную формульную константу а (в теореме 12 была доказана оценка ad>d+1, однако в пределе это не дает лишь тривиальную оценку на а: а >1).
• Доказана Е^ полнота задачи проверки вложения для двух заданных формул над базисом Де Моргана.
• Получены верхние и нижние оценки на топологическое вложение деревьев для различных значений параметров nи к.
• Доказана теорема про сведение вложения в общем случае к топологическому вложению раскрашенных деревьев.
• Доказана характеризация read-once вложения через вложение минтермов и макстермов, и ее обобщение на вложение в общем случае.
• Доказаны оценки на сложность функций Parity и MODpв классической коммуникационной модели и в полудуплексной модели с тишиной.
• Проведено исследование с целью поиска универсальных формул для малых глубин методами компьютерного анализа.
Часть результатов, связанная с оценками на сложность функций в полудуплексных моделях коммуникационной сложности, была опубликована в статье [13], часть про универсальные коммуникационные протоколы готовится к публикации.
Все еще остается открытым вопрос о точной оценке на коэффициент топологического вложения у, а также о какой-нибудь нетривиальной нижней оценке на универсальную формульную константу а (в теореме 12 была доказана оценка ad>d+1, однако в пределе это не дает лишь тривиальную оценку на а: а >1).