Может ли сложение выполняться на глубине менее 5?

Используя алгоритм просмотра с переносом, мы можем вычислить сложение, используя полиномиальный размер семейства цепей 5 (или 4?) . Можно ли уменьшить глубину? Можем ли мы вычислить сложение двух двоичных чисел, используя семейство схем полиномиального размера с глубиной, меньшей глубины, полученной с помощью алгоритма упреждающего просмотра? $AC^0$

Существуют ли суперполиномиальные нижние оценки для размера семейств цепей сложение, где равно 2 или 3? $AC^0_d$ $d$

Под глубиной я подразумеваю глубину чередования.

cc.complexity-theory circuit-complexity lower-bounds upper-bounds анонимное
источник

Можете ли вы сказать нам свое имя? Кто ты? В течение последнего месяца люди делают новое имя пользователя здесь, задают вопрос и затем удаляют это имя пользователя!

Тайфун Pay

@Geekster, обычно люди не обязаны создавать учетную запись или использовать свои настоящие имена (однако это рекомендуется делать по разным причинам). Если у вас есть общее беспокойство о чем-то, пожалуйста, используйте теоретическую компьютерную науку Meta, чтобы поднять это.

Каве

Это можно было бы перебором, проверив, что никакая схема AC

глубине

может вычислить

-битную сумму двух

битных входов для некоторого фиксированного

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

4

$4$

^{0}

$^{0}$

(m + 1)

$(m+1)$

m

$m$

m

$m$

mjqxxxx

@mjqxxxx: Как вы применяете ограничение полиномиального размера для цепей AC0 при грубом форсировании для фиксированного m? @ OP: текущая наилучшая глубина цепи 4 или глубина 5?

Робин Котари

@mjqxxxx: каждая булева функция вычисляется по цепочке глубины

. Теперь предположим, что вы нашли для своего фиксированного

схему размера

. Как вы оцениваете , есть ли размер

схема для каждого

, где

, или есть только схемы размера

, где

? Просто нет способа вывести асимптотическую информацию из конечного примера.

2

$2$

m

$m$

s

$s$

c n

$cn$

n

$n$

c = s / m

$c=s/m$

2^{ϵ n}

$2^{\epsilon n}$

ϵ = (\log s) / m

$\epsilon=(\log s)/m$

Эмиль Йержабек поддерживает Монику

Ответы:

В соответствии с теоремой 3.1 в Пороговых схемах Алексиса Масиэля и Дениса Териена малой глубины большинства действительно существует схема глубины 3 для вычисления сложения двух чисел.

Точная граница где - проблемы, которые имеют глубинные 2 цепи с обоими затворами вверху, а цепи являются цепями глубины один (подробное объяснение обозначений см. в статье). $\Delta_2 \cdot \mathsf{NC}^0_1$ $\Delta_2 = \Sigma_2 \cap \Pi_2$ $\mathsf{AC}^0$ $\vee,\wedge$ $\mathsf{NC}^0_1$ $\mathsf{NC}^0$

Основные идеи доказательства:

Во- первых, выразить Карри-опережения схему как $\mathsf{NC}^0\cdot\Delta_2\cdot\mathsf{NC}^0$
Далее, вызовите закрывающие свойства , чтобы записать это как $\Delta_2$ $\Delta_2\cdot\mathsf{NC}^0$
И, наконец, использовать тот факт (также доказано в работе) , что $\mathsf{NC}^0 \subset \Delta_1\cdot\mathsf{NC}^0_1$

SamiD
источник

Для контуров глубины 2 требуется экспоненциальный размер для вычисления сложения, поскольку контур глубины 2 должен быть либо DNF, либо CNF, и легко проверить, что экспоненциально много минтермов и максимумов.

Предупреждение : часть ниже глючит . Смотрите комментарии под ответом.

Как я считаю, сложение может быть сделано подробно 3. Предположим, что и - это ые биты двух чисел, где - это индекс LSB и MSB. $a_i$ $b_i$ $i$ $0$ $n$

Давайте вычислим й бит суммы, стандартным способом, с переносом в будущее: $i$ $s_i$

s_{i} = a_{i} \oplus b_{i} \oplus c_{i}

$s_i = a_i \oplus b_i \oplus c_i$

где - XOR, а - перенос, вычисленный как: $\oplus$ $c_i$

c_{i} = \underset{j ∣ j < i}{⋁} (g_{j} \land p_{j})

$c_i = \bigvee_{j\mid j < i} (g_j \wedge p_j)$

и означает, что е местоположение «сгенерировало» перенос: $g_j$ $j$

g_{j} = (a_{j} \land b_{j})

$g_j = (a_j \wedge b_j)$

и означает, что перенос переносится из в : $p_j$ $j$ $i$

p_{j} = \underset{k ∣ j < k < i}{⋀} (a_{j} \lor b_{j})

$p_j = \bigwedge_{k\mid j < k < i} (a_j \vee b_j)$

Считая глубину, - это глубина 2, а - это глубина 3. Хотя может показаться, что - это глубина 4 или 5, на самом деле это также всего лишь глубина 3, так как это ограниченное вычисление веером для схем глубины 3, поэтому может сдвинуть верхние два уровня вниз, используя формулы де-Моргана, в то же время увеличивая размер схемы на полиномиальную величину. $p_j$ $c_i$ $s_i$

Ноам
источник

Я не совсем понимаю, как ограниченное вычисление вентиляторов для схем глубины 3 автоматически становится глубиной 3. Если, скажем, вы пишете

как

, вы можете сделать первый дизъюнктный контур глубиной 3 с

сверху, а второй дизъюнктный контур глубины 3 с

s_{i}

$s_i$

(c_{i} \land \neg (a_{i} \oplus b_{i})) \lor (\neg c_{i} \land (a_{i} \oplus b_{i}))

$(c_i\land\neg(a_i\oplus b_i))\lor(\neg c_i\land(a_i\oplus b_i))$

⋁

$\bigvee$

⋀

$\bigwedge$ наверху. Я не вижу, как толкнуть верхнюю дизъюнкцию, не увеличивая глубину на единицу, чтобы учесть несоответствие между типами соединений в двух частях. Это можно исправить, отметив, что

также можно вычислить по-другому с помощью схемы глубины 3 ...

c_{i}

$c_i$

Эмиль Йержабек поддерживает Монику

... с

сверху. С другой стороны, все контуры глубины 3 имеют ограниченный нижний разветвитель, поэтому я бы назвал их глубиной 2 1/2.

⋀

$\bigwedge$

Эмиль Йержабек поддерживает Монику

Это очевидно. То , что я хочу подчеркнуть, что , как написано, вы не должны здесь ОШ двух глубины

цепей с и на вершине. У вас есть ИЛИ двух глубинных

цепей, одна из которых имеет И в верхней части, а другая ИЛИ в верхней части. Я сомневаюсь, что такие схемы могут быть преобразованы в глубину

в целом. Думайте о полиномиальных разветвлениях AND и OR как квантификаторах. Вы можете выразить

d

$d$

d

$d$

d

$d$

как формула перед пренексом с

блоками квантификаторов, нодля выражениявам нужно

блоков ...

(\forall x_{1} \exists x_{2} \dots Q x_{d} ϕ (x_{1}, \dots, x_{d})) \lor (\forall x_{1} \exists x_{2} \dots Q x_{d} ψ (x_{1}, \dots, x_{d}))

$(\forall x_1\exists x_2\dots Qx_d\phi(x_1,\dots,x_d))\lor(\forall x_1\exists x_2\dots Qx_d\psi(x_1,\dots,x_d))$

d

$d$

d + 1

$d+1$

Эмиль Йержабек поддерживает Монику

... формула

(\forall x_{1} \exists x_{2} \dots Q x_{d} ϕ (x_{1}, \dots, x_{d})) \lor (\exists x_{1} \forall x_{2} \dots \bar{Q} x_{d} ϕ (x_{1}, \dots, x_{d}))

$(\forall x_1\exists x_2\dots Qx_d\phi(x_1,\dots,x_d))\lor(\exists x_1\forall x_2\dots \overline Qx_d\phi(x_1,\dots,x_d))$

Эмиль Йержабек поддерживает Монику

Для явного контрпримера к общему принципу пусть

- семейство функций, вычисляемых по

цепям с OR на вершине, требующих суперполиномиальной глубины

цепей с AND на вершине (например, функции Sipser). Тогда

не имеют

цепей. Предположим для противоречия, что

f_{n} (x_{1}, \dots, x_{n})

$f_n(x_1,\dots,x_n)$

A C_{d}^{0}

$AC^0_d$

d

$d$

x_{0} \oplus f_{n}

$x_0\oplus f_n$

A C_{d}^{0}

$AC^0_d$

C_{n} (x_{0}, \dots, x_{n})

$C_n(x_0,\dots,x_n)$ являются такими цепями, и что

имеет ИЛИ на вершине (другой случай является симметричным). При установке

, получим

схемы для

с или на вершине, следовательно

схем для

с и на вершине, противоречие.

C_{n}

$C_n$

x_{0} = 1

$x_0=1$

A C_{d}^{0}

$AC^0_d$

\neg f_{n}

$\neg f_n$

A C_{d}^{0}

$AC^0_d$

f_{n}

$f_n$

Эмиль Йержабек поддерживает Монику