Является ли

В опросе Д. Бера, Ф. Грина и С. Гомера «Квантовые схемы малой глубины» (стр. 36 ACM SIGACT News, июнь 2007 г., том 38, № 2) я прочитал следующее предложение:

Классическая версия (в которой вентили и имеют самое большее постоянное разветвление), очевидно, слабее, чем .$QAC^0$$AND$$OR$$AC^0$

Ссылка на это требование отсутствует. Я назову этот класс , где означает «ограниченное разветвление». (Зоопарк Сложности закрыт, и я не могу проверить, есть ли такой класс в литературе). Если мы предположим неограниченное разветвление для входных битов, то эти схемы кажутся эквивалентными формулам с постоянной глубиной вплоть до полиномиального увеличения размера, поэтому приведенное выше утверждение не имеет смысла. Вместо этого, если мы предполагаем ограниченный разветвление для входных битов, то я не могу думать ни о каком языке, который отделяет этот класс от . Возможным кандидатом может быть язык , т. е. язык строк только с одним. Это легко показать$AC^0_{bf}$$bf$$AC^0$$X := \{x | \mbox{weight}(x) = 1 \}$$X \in AC^{0}$ , но мне не удалось доказать, что .$X \notin AC^{0}_{bf}$

Вопросы:

Действительно ли слабее, чем ? Если да, то есть какая-нибудь идея или какая-либо ссылка на то, как это доказать? И что это за язык, который разделяет эти два класса? А как насчет ?$AC^0_{bf}$$AC^0$$X$

Ограничение разветвления входных битов и вентилей сделает размер схемы линейным. Пусть будет границей разветвления ворот и входов. Это DAG с максимальной степенью выхода, ограниченной k, и максимальной длиной пути d . Количество доступных проводов на каждом уровне можно увеличить K раз, и количество доступных проводов на вершине к п , так что общее количество проводов в цепи не превосходит к п Е д я = 0 K я ≤ K d + 1 n, который является O ( n ) .$k$$k$$d$$k$$kn$$kn \sum_{i=0}^d k^i \leq k^{d+1} n$$O(n)$

Любая функция которая требует суперлинейного размера, будет отделять класс функций с ограниченным разветвлением (также применяется к входным битам) от A C 0 . Вот некоторые примеры:$\mathsf{AC^0}$$\mathsf{AC^0}$

1. [CR96]: функция которой требуется суперлинейный размер, равна 1$\mathsf{AC^0}$ приблизительный селектор$\frac{1}{4}$. А -приближенный селектор - это любая функция, значение которой равно:$\frac{1}{4}$

   • всякий раз, когда число 1 с не более$0$$1$ ,$\frac{n}{4}$
   • всякий раз, когда число 0 с не более$1$$0$ ,$\frac{n}{4}$
   • в противном случае может быть или 1 .$0$$1$

2. [Ros08] показывает, что клик имеет сложность функций A C 0 n Θ ( k ) ( n 2 входных битов являются возможными ребрами графа с n вершинами). Это дает нижний предел размера суперлинии при k > 2 .$k$$\mathsf{AC^0}$$n^{\Theta(k)}$$n^2$$n$$k\gt 2$

3. Вероятно, можно обобщить пример в 2 банках на существование любой нетривиальной (требующей более одного бита) фиксированной индуцированной подструктуры в данной неупорядоченной структуре, например:

   • существование пути длины 2 в данном графе,
   • ,$\#_1(x)=2$

   поскольку они требуют суперконстантного числа вентилей в зависимости от бита, что невозможно в .$\mathsf{AC^0_{bf}}$

4. Самым простым примером является шлюз дубликатора, то есть шлюз, который создает копии своего входного бита. Это невозможно в A C 0 b f, поскольку только O ( 1 ) вентилей может зависеть от каждого входного бита.$\omega(1)$$\mathsf{AC^0_{bf}}$$O(1)$

Также любая схема размера S может быть превращена в формулу размера не более k d S и, следовательно, имеет формулу A C 0 b f размера k 2 d + 1 n, поэтому любая функция суперлинейного A C 0 Сложность формулы не будет в A C 0 b f .$\mathsf{AC^0_{bf}}$$S$$k^dS$$\mathsf{AC^0_{bf}}$$k^{2d+1}n$$\mathsf{AC^0}$$\mathsf{AC^0_{bf}}$

Ссылки:

[CR96] С. Чаудхури и Дж. Радхакришнан, « Детерминированные ограничения в сложности схем », 1996

[Ros08] Бенджамин Россман, " О постоянной глубине сложности k-Clique ", 2008

[Juk] Стасис Юкна, « Сложность булевой функции: достижения и границы », черновик