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

13

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

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

matthon
источник
6
Это может быть интересно: Игорь Сергеев, Верхние оценки для размера формулы функции большинства ; также здесь он объявляет немного лучшие верхние границы. Однако, если вы спросите только о схемах (не формулах ), то, как напомнил мне Игорь, каждая симметричная логическая функция (а не только большинство) имеет схему глубины и размера O ( n ) : просто вычислите сумму 1 с, и реализовать булеву функцию от log 2 n переменных. Для большинства эта последняя функция является сравнением с пO(logn)O(n)1log2n . n/2
Стасис
@Stasys, и вычисление количества единиц по существу сортирует биты.
Каве

Ответы:

9

Ответ Каве дает ответ на вопрос в том виде, в котором вы его сформулировали (и это обычное доказательство того, что содержится в N C 1 ). Но я подумала, что вы, возможно, намеревались задать немного другой вопрос. А именно для явного полиномиального размера монотонной формулы для большинства.TC0NC1

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

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

Кристоффер Арнсфельт Хансен
источник
9

Вычисление порога ворот ограничено ( ), по существу , сортировка входных битов.ixik

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

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

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

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


AC0AC1NC2

O(lgn)


a,b,cx,ya+b+c=x+y

O(1)

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

Кава
источник
O(lgn)O(lgn)