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

21

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

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

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

анонимное
источник
Можете ли вы сказать нам свое имя? Кто ты? В течение последнего месяца люди делают новое имя пользователя здесь, задают вопрос и затем удаляют это имя пользователя!
Тайфун Pay
14
@Geekster, обычно люди не обязаны создавать учетную запись или использовать свои настоящие имена (однако это рекомендуется делать по разным причинам). Если у вас есть общее беспокойство о чем-то, пожалуйста, используйте теоретическую компьютерную науку Meta, чтобы поднять это.
Каве
4
Это можно было бы перебором, проверив, что никакая схема AC 0 на глубине может вычислить ( m + 1 ) -битную сумму двух m- битных входов для некоторого фиксированного m ; Есть только конечное число логических функций входных битов, которые могут появляться на каждой глубине. 40(m+1)mm
mjqxxxx
5
@mjqxxxx: Как вы применяете ограничение полиномиального размера для цепей AC0 при грубом форсировании для фиксированного m? @ OP: текущая наилучшая глубина цепи 4 или глубина 5?
Робин Котари
14
@mjqxxxx: каждая булева функция вычисляется по цепочке глубины . Теперь предположим, что вы нашли для своего фиксированного m схему размера s . Как вы оцениваете , есть ли размер с п схема для каждого п , где с = s / м , или есть только схемы размера 2 ε п , где ε = ( бревна сек ) / м ? Просто нет способа вывести асимптотическую информацию из конечного примера. 2mscnnc=s/m2ϵnϵ=(logs)/m
Эмиль Йержабек поддерживает Монику

Ответы:

13

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

Точная граница где Δ 2 = Σ 2Π 2 - проблемы, которые имеют глубинные 2 A C 0 цепи с обоими , затворами вверху, а N C 0 1 цепи являются N C 0 цепями глубины один (подробное объяснение обозначений см. в статье).Δ2NC10Δ2=Σ2Π2AC0,NC10NC0

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

  • Во- первых, выразить Карри-опережения схему как NC0Δ2NC0
  • Далее, вызовите закрывающие свойства , чтобы записать это как Д 2Н С 0Δ2Δ2NC0
  • И, наконец, использовать тот факт (также доказано в работе) , что NC0Δ1NC10
SamiD
источник
9

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

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

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

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

si=aibici

где - XOR, а c i - перенос, вычисленный как:ci

ci=jj<i(gjpj)

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

gj=(ajbj)

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

pj=kj<k<i(ajbj)

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

Ноам
источник
4
Я не совсем понимаю, как ограниченное вычисление вентиляторов для схем глубины 3 автоматически становится глубиной 3. Если, скажем, вы пишете как ( c i¬ ( a ib i ) ) ( ¬ c i( a ib i ) ) , вы можете сделать первый дизъюнктный контур глубиной 3 с сверху, а второй дизъюнктный контур глубины 3 с withsi(ci¬(aibi))(¬ci(aibi))наверху. Я не вижу, как толкнуть верхнюю дизъюнкцию, не увеличивая глубину на единицу, чтобы учесть несоответствие между типами соединений в двух частях. Это можно исправить, отметив, что также можно вычислить по-другому с помощью схемы глубины 3 ...ci
Эмиль Йержабек поддерживает Монику
1
... с сверху. С другой стороны, все контуры глубины 3 имеют ограниченный нижний разветвитель, поэтому я бы назвал их глубиной 2 1/2.
Эмиль Йержабек поддерживает Монику
1
Это очевидно. То , что я хочу подчеркнуть, что , как написано, вы не должны здесь ОШ двух глубины цепей с и на вершине. У вас есть ИЛИ двух глубинных d- цепей, одна из которых имеет И в верхней части, а другая ИЛИ в верхней части. Я сомневаюсь, что такие схемы могут быть преобразованы в глубину d в целом. Думайте о полиномиальных разветвлениях AND и OR как квантификаторах. Вы можете выразить ( x 1x 2Q x d ϕ ( x 1 , , x d ) ) ( xddd как формула перед пренексом с d блоками квантификаторов, нодля выражениявам нужно d + 1 блоков ...(x1x2Qxdϕ(x1,,xd))(x1x2Qxdψ(x1,,xd))dd+1
Эмиль Йержабек поддерживает Монику
1
... формула . (x1x2Qxdϕ(x1,,xd))(x1x2Q¯xdϕ(x1,,xd))
Эмиль Йержабек поддерживает Монику
5
Для явного контрпримера к общему принципу пусть - семейство функций, вычисляемых по A C 0 d цепям с OR на вершине, требующих суперполиномиальной глубины d цепей с AND на вершине (например, функции Sipser). Тогда x 0f n не имеют A C 0 d цепей. Предположим для противоречия, что C n ( x 0 , , x n )fn(x1,,xn)ACd0dx0fnACd0Cn(x0,,xn)являются такими цепями, и что имеет ИЛИ на вершине (другой случай является симметричным). При установке х 0 = 1 , получим C 0 D схемы для ¬ е н с или на вершине, следовательно С 0 д схем для е н с и на вершине, противоречие. Cnx0=1ACd0¬fnACd0fn
Эмиль Йержабек поддерживает Монику