Обзор высокого уровня метода приближений Разборова

Что такое метод приближений Разборова? Может ли кто-нибудь дать обзор высокого уровня и интуицию, стоящую за ним?

Пусть - булева функция на -битах. Пусть . Пусть будет цепью из n битов размером и вентилями . также обозначает функцию на битах, вычисленную подсхемой с в качестве последнего элемента. Первые вентилей предназначены для ввода . Цель состоит в том, чтобы показать, что размера не может вычислить . Рассмотрим все вычисления на входах из$f$$n$$Z = f^{-1}(0) \subseteq 2^n$$C$$m$$g_1, \ldots, g_m$$g_i$$n$$g_i$$n$$x_1, \ldots, x_n$$C$$m$$f$$C$$Z$, Вычисление присваивает значения выходам ворот. Пусть - булева алгебра в .$B$$P(Z)$

Идея заключается в том , чтобы рассмотреть для любой функции на -bits , насколько хорошо аппроксимирует на . Пусть .$g$$n$$f$$Z$$||g|| = \{w \in Z \mid g(w) \neq 0 \}$

Для ультрафильтра мы можем определить новое вычисление по ультрапродукту из него: тогда и только тогда, когда . Поскольку ультрафильтр, по сути, представляет собой набор последовательных вычислений для значений 0, полученный является допустимым вычислением. Из этого следует, что . Мы создали новое вычисление из существующих. Поскольку все Ультрафильтры на конечных множествах являются главными . Это работает для любой схемы, мы не использовали тот факт, что схема имеет размер .$F \subseteq B$$c(g_i) = 0$$||g_i|| \not\in F$$c$$f(c_1, \ldots, c_n) = 0$$c_1,\ldots,c_n \in Z$$m$

Следующая идея теперь состоит в том, чтобы использовать конечность схемы для создания нового входа, который находится за пределами и но схема не замечает из-за своего ограниченного размера и, следовательно, все еще выводит 0. Поэтому он не вычислить .$Z$$f(w) \neq 0$$f$

Нам нужно расслабить определение ультрафильтрации , так что мы можем получить вход снаружи . Вместо ультрафильтров мы используем замкнутые вверх подмножества ( и подразумевает ), которые сохраняют встретимость ( подразумевает ).$Z$$B$$a \in F$$a \subseteq b$$b \in F$$a,b \in F$$a \cap b \in F$

Пусть . есть множество входов в соответствии с . Если является простым ( влечет или ) и nonfull ( ) , то для каждого , содержит либо илии содержит только один вход.$W_F = \{w \in 2^n \mid w_i = 0 \to ||\lnot x_i|| \in F, w_i \neq 0 \to ||x_i|| \in F\}$$W_F$$F$$F$$a \cup b \in F$$a \in F$$b \in F$$\emptyset \not\in F$$i$$F$$||x_i||$$||\lnot x_i||$$W_F$

Мы собираемся расслабить сохранение встреч. Вместо всех встреч в булевой алгебре мы сохраним небольшое их количество. Пустьнаименьшее число от того, соответствует , что для всех вверх-закрыто, nonfull, -preserving , .$|f|$$k$$M = (a_1 \cap b_1, \ldots, a_k \cap b_k)$$M$$F$$W_F \subseteq Z$

Пусть будет сложностью схемы . Разборов доказал, что .$m$$f$$\frac{1}{2}|f| \leq m \leq O(|f|^3 + n^3)$

Отметим, что это неравенство выполняется для всех функций. Чтобы доказать размер цепи нижняя грань , показывают , что для всех -meets , есть , который удовлетворяет условиям , но его не содержится в . Более того, любая нижняя граница сильной цепи может быть доказана этим методом из-за второго неравенства.$m$$m$$M$$F$$W_F$$Z$

Фактическая часть схемы нижней грани доказательства , чтобы показать , что при заданном , для любого -meets есть такая . В случае монотонных цепей условие относительно упрощается до поэтому придумывать проще.$m$$m$$F$$W_F$$w_i \neq 0 \to ||x_i|| \in F$$F$

Александр Разборов, О методе аппроксимации, 1989. pdf

Маурисио Карчмер, Доказательство нижних границ для размера схемы, 1995.

Тим Гауэрс, Метод приближения Разборова, 2009. pdf

Отказ от ответственности : это только общий обзор, предназначенный для того, чтобы дать некоторое представление о методах, использованных в недавней статье Блума.

Я попытаюсь использовать обозначения, которые ближе к тому, что используется в вышеупомянутой статье.

Пусть - булева функция от переменных . Предположим, мы хотим доказать, что любые булевы сетевые вычисления имеют большой размер.$f$$n$$x_1,\dots,x_n$$f$

Учитывая некоторую булеву сеть вычисления на своем выходном узле, рассмотрим следующий процесс.$\beta$$f$

1. ворота в согласно некоторому топологическому порядку где последний узел является выходным узлом.$\beta$$g_1,g_2,\dots,g_m$
2. Для каждого временного шага мы будем аппроксимировать функцию, вычисленную в воротах , «простой» функцией . Это приближение может изменить функции, вычисленные в узлах ниже по течению от (в частности, функция в выходном узле могла измениться).$t=1,\dots,m$$g_t$$f_{g_t}$$g_t$$g_m$

В конце этого процесса мы аппроксимируем функцию, вычисленную в , простой функцией .$g_m$$f_{g_m}$

Далее создайте группу тестовых входов .$T\subseteq \{0,1\}^n$

Предположим, мы можем доказать следующие утверждения:

• Аппроксимация каждого отдельного узла является хорошей (то есть, на большинстве входов от на каждом шаге аппроксимации вводится самое большее количество ошибок ).$e$$T$
• Ни одна простая функция не приближается к хорошо (т. Для любой простой функции , мы имеем на более чем -фракции ).$f$$f_{g_m}$$f_{g_m}\neq f$$d$$T$

Затем, просто посчитав количество ошибок, мы получим, что должно иметь как минимум -много ворот.$\beta$$\tfrac{d\lvert T\rvert}{e}$

Если можно показать, что эта схема аппроксимации работает для любой сети вычисляющей функцию , то мы приходим к нижней границе сложности схемы .$\beta$$f$$f$