Минимальная ширина дерева цепи для большинства

Какова минимальная ширина дерева схемы над для вычисления MAJ?$\{\wedge,\vee,\neg\}$

Здесь MAJ выводит 1, если хотя бы половина его входов равна .$:\{0,1\}^n \rightarrow \{0,1\}$$1$

Я забочусь только о размере схемы (должен быть полиномиальным) и о том, что вход должен быть прочитан только один раз, хотя разветвление входного вентиля может быть произвольным (это решающим образом влияет на ширину дерева схемы - ветвление программы, полученные из теоремы Баррингтона из MAJ , интерпретируемые как косые схемы, не помогают). И, конечно, ширина дерева - самая важная вещь. Я не забочусь о глубине или любого другого параметра.N C$\in$ $\mathsf{NC}^1$

Некоторые из общих схем для MAJ включают в себя:

• Схемы дерева Уоллеса (например, теорема 8.9 здесь ), которые используют трюк 3-в-2, чтобы поместить MAJ в ?$\mathsf{NC}^1$
• Монотонные схемы Валианта для MAJ (например, теорема 4 здесь )$\mathsf{NC}^1$
• $\log^{O(1)}{n}$ сеть сортировки по глубине, такая как сортировка с дозатором
• АКС Сортировочная сеть

У любого из них есть ограниченная или даже полилогарифмическая ширина дерева?

Или на самом деле,

Есть ли основания полагать, что для MAJ нет ограниченных схем шириной дерева?

Обратите внимание, что каждая функция, вычисленная с помощью ограниченной схемы ширины дерева, может быть вычислена с помощью схемы , даже если нет условия однократного чтения через JansenSarma . Таким образом, неправдоподобие такого семейства цепей будет указывать на то, что эта граница может быть ужесточена в случае схем с однократным чтением.$\mathsf{NC}^1$

Отвечая на половину вопроса Самира.

Пусть быть ДАГ и два подмножества вершин . Обозначим через множество всех ребер в с одной конечной точкой в и другой конечной точкой в . Если - полное упорядочение вершин то пусть обозначает ширину . Онлайн-ширина определяется как $G=(V,E)$$V_1,V_2\subseteq V$$G$$E(V_1,V_2)$$G$$V_1$$V_2$$\omega = (v_1,...,v_n)$$G$

$$\mathbf{ow}(G,\omega) = \max_{i}\; |E(\{v_1,...,v_i\},\{v_{i+1},...,v_n\}|$$ $\omega$$G$ $$\mathbf{ow}(G) = \min_{\omega}\; \mathbf{ow}(G,\omega),$$ где минимум берется по всем топологическим упорядочениям вершин . Обратите внимание, что традиционное понятие ширины среза , определяется аналогично, за исключением того, что минимум берется по всем возможным порядкам , независимо от того, является ли порядок топологическим или нет. У нас есть следующая последовательность неравенств: где , и , являются , соответственно, pathwidth и древесная ширина из .$G$$G$$\mathbf{cw}(G)$$G$ $$\mathbf{tw}(G) \leq \mathbf{pw}(G) \leq \mathbf{cw}(G)\leq \mathbf{ow}(G),$$ $\mathbf{pw}(G)$$\mathbf{tw}(G)$$G$

Мы утверждаем, что БОЛЬШИНСТВО бит может быть вычислено в онлайн-ширине и, следовательно, в трехчастотном . Схема моделирует оперативный алгоритм, который считывает один входной бит за раз и добавляет к счетчику с битами тогда и только тогда, когда . В начале счетчик инициализируется до$n$$O(\log n)$$O(\log n)$$b$$b$$O(\log n)$$b=1$$0$, В конце схема принимает, если и только если значение счетчика больше, чем n / 2. Легко видеть, что затворы схемы ADD, которая добавляет единицу в регистр счетчика, можно топологически упорядочить таким образом, чтобы он имел постоянную ширину в сети, поскольку для этих схем просто необходимо реализовать операцию переноса. Общая схема представляет собой последовательность цепей где выход подключен к входу , а выход подключен к ввод КОМП. Теперь, если мы топологически упорядочим общую схему таким образом, что все ворота появятся перед воротами и всеми воротами$C=(ADD_1,ADD_2,...,ADD_n,COMP)$$ADD_i$$ADD_{i+1}$$ADD_n$$C$$ADD_i$$ADD_{i+1}$$ADD_n$ появляются перед воротами COMP, тогда этот топологический порядок имеет оперативную ширину . Эта конструкция проиллюстрирована на рисунке 1 моей бумаги, чтобы показать, что усиление вероятности может быть сделано в логарифмической онлайн-ширине.$O(\log n)$

Obs: Глубина контура C составляет .$O(n)$

Отвечая на другую половину вопроса - вот пример доказательства для нижней границы для ширины дерева для некоторой константы . Граница не зависит от размера или любого другого аспекта схемы. В остальной части аргумента - это схема, - это длина дерева а - это количество входных вентилей.$c \cdot \log n$$c$$C$$t$$C$$n$

Первым шагом является использование леммы о сбалансированном разделителе для графиков ограниченной длины деревьев . Затворы (включая входные затворы) схемы могут быть разделены на три части , и , так что и и содержат по крайней меревходные ворота, и нет дуг (провода) между и .$L$$R$$S$$|S| \leq t+1$$L$$R$$n/3-|S|$$L$$R$

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

Имея под рукой, мы построим схему из следующим образом: для каждого вентиля в сделайте еще два и и сделайте и в . Для всех проводов, ведущих в из сделайте их вместо этого в . Для всех проводов, ведущих в от сделайте их вместо этого в . Пусть $(L,S,R)$$C'$$C$$g$$S$$g_L$$g_R$$g_L$$g_R$$g$$g$$L$$g_L$$g$$R$$g_R$

$$S' = \{g, g_L, g_R : g \in S\}.$$

Для каждого из обозначений создайте схему, которая выводит 1, если (a) назначение входных вентилей делает вывод истинным и (b) назначение входным вентилям устанавливает все Ворота как и предполагалось. Назовите эти схемы , , для . Обратите внимание, что схема естественно разбивается на две подсхемы и , так что зависит только от входных вентилей , зависит только от входных вентилей$2^{|S'|}$$S'$$C'$$S'$$C_1$$C_2$$C_3 \ldots C_x$$x \leq 8^t$$C_i$$C_i^L$$C_i^R$$C_i^L$$L \cup S'$$C_i^R$$R \cup S'$ , и для любого назначения на входных воротах у нас есть , что .$C_i = C_i^L \wedge C_i^R$

Поскольку каждое назначение входных вентилей согласуется с некоторым предположением о том, что происходит в мы имеем . Таким образом, мы переписали схему как ИЛИ (из fanin ) из AND (из fanin ), где номер логического элемента AND подается на выход и соответственно.$S'$$C' = C_1 \vee C_2 \vee C_3 \ldots \vee C_x$$C$$8^t$$2$$i$$C_i^L$$C_i^R$

Пусть будет множеством верхних И-ворот. Сначала докажем, что, Это дает простой нижний предел для . Затем мы докажем лучшую оценку.$Z$$2^{|Z|} \geq n/3-|S|$$\log \log n$$t$

---

Предположим, чтоИ предположим , что без потери общности содержит меньше , чем входные ворота . Тогда и и содержат хотя бывходные ворота. По принципу голубиного отверстия есть два разных числа и , так что есть два разных назначения для входных вентилей , одно, которое устанавливает gates в true, другое , устанавливающее , так что схемы , все выводят одно и то же. Но существует назначение для входных ворот в$2^{|Z|} < n/3-|S|$$L$$R$$L$$R$$n/3-|S|$$i$$j$$L$$i$$j$$C_1^L$$C_2^L \ldots C_x^L$$R$таким образом, что MAJORITY выдает FALSE, если для логических элементов в задано значение true, а MAJORITY выдает TRUE, если для элементов в установлено значение true. Это противоречие, и поэтому подразумевая, что длина дерева не меньше .$i$$L$$j$$L$$2^{|Z|} \geq n/3-|S|$$\log \log n$

---

Теперь покажем лучшую оценку:, Предположим , что без потери общности содержит меньше , чем входные ворота . Тогда и L, и R содержат хотя бывходные ворота. Рассмотрим «все ложные» отнесение к . Пусть будет наименьшим числом входных вентилей , которое должно быть установлено в true, так что MAJ выводит TRUE, учитывая, что все установлены в false.$|Z| \geq n/3-|S|$$L$$R$$n/3-|S|$$L$$r$$R$$L$

Поскольку установка для всех ложного и ровно входных ворот , чтобы истинная марка мажоритарного выход там должен быть некоторым таким образом, что выводит значение TRUE, без потери общности , это . Все присвоения с меньшим , чем истинных входных ворот необходимо установить к ложным. Поскольку установка входного вентиля в значение true и входных вентилей в значение true приводит к выводу MAJORITY , установка вентиля в значение true должна составлять хотя бы один$L$$r$$R$$1$$i$$C_i^L$$C_1^L$$R$$r$$C_1^R$$1$$L$$r-1$$R$$1$$1$$L$$C_i^L$ превосходит истину для . Wlog мы можем предположить, что . Тогда все присваивания которые устанавливают не более входных вентилей на true, должны установить в false, и так далее - мы можем повторить этот аргумент раз. Но это означает, что, давая нижнюю оценку для .$i \neq 1$$i=2$$R$$r-2$$C_2^R$$r$$|Z| \geq r \geq n/3-|S|$$c \cdot \log n$$t$

[Я знаю, что этот эскиз немного местами волнистый, спросите, если что-то неясно ...]