Сложность схемы функции большинства

Пусть - мажоритарная функция, т.е. f ( x ) = 1 тогда и только тогда, когда ∑ n i = 1 x i > n / 2 . Мне было интересно, есть ли простое доказательство следующего факта (под «простым» я подразумеваю не полагаться на вероятностный метод, как это сделал Valiant 84, или на сортировку сетей; предпочтительно предоставление явного, простого построения схемы):$f: \{0,1\}^n \to \{0,1\}$$f(x) = 1$$\sum_{i = 1}^n x_i > n/2$

может быть вычислено семейством схемглубиной O ( log ( n ) ) , размером poly (n), где вентили состоят из вентилей NOT, вентилей OR с 2 входами и вентилей AND с 2 входами.$f$$O(\log(n))$

Ответ Каве дает ответ на вопрос в том виде, в котором вы его сформулировали (и это обычное доказательство того, что содержится в N C 1 ). Но я подумала, что вы, возможно, намеревались задать немного другой вопрос. А именно для явного полиномиального размера монотонной формулы для большинства.$\mathsf{TC}^0$$\mathsf{NC}^1$

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

С этим также связано следующее. Оказывается, что большинство можно вычислить по формулам, состоящим только из вентилей (и без констант!). Вероятностная конструкция Валианта может быть адаптирована для получения таких формул глубины O ( log ( n ) ) . Однако здесь мы не знаем никакой детерминированной конструкции. В частности, сортировочные сети не подходят для этого (техническая причина: они будут обеспечивать все пороговые функции, и только вентильные функции могут быть вычислены с помощью M A J 3 вентилей). Однако в этом вопросе в последнее время достигнут прогресс$\mathsf{MAJ}_3$$O(\log(n))$$\mathsf{MAJ}_3$Эффективные многопартийные протоколы с помощью пороговых формул логарифмической глубины Cohen et al. Здесь такие формулы построены на основе стандартных теоретико-сложных или криптографических предположений.

Вычисление порога ворот ограничено ( ), по существу , сортировка входных битов.$\sum_i x_i \geq k$

Если вы можете отсортировать биты, тогда легко сравнить результат с и вычислить ограниченный порог.$k$

С другой стороны, предположим, что у нас есть схемы для вычисления ограниченного порога. Мы можем выполнить параллельный поиск, чтобы найти количество единиц на входе и вывести отсортированный список.

Они сохраняют глубину цепи. Так что, если вы придумаете новую схему для вычисления ограниченного порога, то это даст схему сортировки глубины O ( lg n ) . Так что, если мы придумаем простой аргумент для того, чтобы показать, что большинство в$\mathsf{NC^1}$$O(\lg n)$ вы нашли простой depth- O ( Л.Г. п ) цепь (кроме одной на основе АКС сортировочных сети) сортировки.$\mathsf{NC^1}$$O(\lg n)$

Обратите внимание, что легко реализовать ограниченный порог, используя большинство, добавив новые входы 1 и 0 в шлюз большинства.

$\mathsf{AC^0}$$\mathsf{AC^1}$$\mathsf{NC^2}$

$O(\lg n)$

$a,b,c$$x,y$$a+b+c = x+y$

$O(1)$

Смотрите раздел 4 и упражнение 4 в

• Дэвид Микс Баррингтон и Алексис Макиэль, « Продвинутый курс по вычислительной сложности », лекция 6, IAS / PCMI, 2000.

$n$

Альтернативное доказательство дано Бродалом и Хусфельдтом: Сложность связи. Доказательство того, что симметричные функции имеют логарифмическую глубину . Опять же, доказательство элементарно и дает явную конструкцию.