Арифметические схемы с одним порогом

21

Когда ограничение ограничено - входами, каждая -схема вычисляет некоторую функцию . Чтобы получить булеву функцию, мы можем просто добавить один пороговый вентиль fanin-1 в качестве выходного вентиля. На входе результирующая пороговая схема - выводит если , и выдает если ; порог может быть любым положительным целым числом, которое может зависеть от0 1 { + , × } F ( x 1 , , x n ) F : { 0 , 1 } nN01{+,×}F(x1,,xn)F:{0,1}nNa { 0 , 1 } na{0,1}n { + , × }{+,×}1 F ( a ) t 0 F ( a ) t - 1 t = t n n1F(a)t0F(a)t1t=tnnно не на входных значениях. Результирующая схема вычисляет некоторую (монотонную) булеву функцию .F : { 0 , 1 } n{ 0 , 1 }F:{0,1}n{0,1}

Вопрос: Может ли пороговая -цепь эффективно моделироваться -цепью? { + , × } { , }{+,×}{,}

Под «эффективно» я подразумеваю «с максимальным полиномиальным увеличением размера». Ответ ясен "да" для порога : просто замените на \ lor , \ times на \ land и удалите последние пороговые значения. То есть \ {\ lor, \ land \} -схемы на самом деле являются пороговыми- 1 \ {+, \ times \} -схемами. Но как насчет больших порогов, скажем, t = 2 ? t = 1 + × { , } 1 { + , × } t = 2t=1+×{,}1 {+,×}t=2

Можно определить арифметические аналоги # C#C большинства классов логических цепей СC , просто используя ++ вместо OR, ×× вместо AND и 1 - х я1xi вместо ˉ х яx¯i . Например, схемы # A C 0#AC0 являются { + , × }{+,×} -схемами постоянной глубины с неограниченными вентилями fanin ++ и ×× и входами х яxi и 1 - х я1xi . Агравал, Аллендер и Датта показали, что порог # A C 0#AC0 = T C 0TC0 . (Напомним, что A C 0AC0 сам по себе является правильнымподмножество T C 0TC0 ; возьмем, скажем, функцию Majority.) Другими словами, пороговые схемы постоянной глубины могут быть эффективно смоделированы цепями { + , - , × }{+,,×} глубины только с одним пороговым затвором! Обратите внимание, однако, что мой вопрос о монотонных схемах (без минуса " - " в качестве затворов и даже без 1 - х я1xi качестве входов). Может ли один (последний) порог ворот быть таким мощным и тогда? Я не знаю этого материала, поэтому любые связанные указатели приветствуются.

NB. Есть еще один интересный результат, связанный с Арнольдом Розенблумом: { + , ×}{+,×} -цепи с одной монотонной функцией г : N 2{ 0 , 1 }g:N2{0,1} качестве выходных элементов вычислить каждую функцию среза с О ( n )O(n) вентилями. Функция слайса - это монотонная логическая функция, которая для некоторого фиксированного Кk выводит 00 (соответственно 11 ) на всех входах с меньшим (соответственно, больше), чем Кk . С другой стороны, простой подсчет показывает, что большинству функций слайса требуются общие { , , ¬ }{,,¬} -схемы экспоненциального размера. Таким образом, один «невинный» дополнительный выходной шлюз можетсделать монотонные схемы всемогущими! Мой вопрос спрашивает, может ли это также произойти, когда g : N{ 0 , 1 }g:N{0,1} является пороговым вентилем fanin- 11 .


АКТУАЛИЗАЦИЯ (добавлено 03.11.2014): Эмиль Йержабек показал (с помощью удивительно простой конструкции, см. Его ответ ниже), что ответ «да», если t n ctnc для константы сc . Таким образом, вопрос остается открытым только для суперполиномиальных (по Nn ) порогов.

Обычно в приложениях работают только большие пороги: нам обычно нужны пороги вида для . Скажем, если считает количество - путей в графе, заданное входом - , то для с , то беспороговый версия решает существование гамильтоновой - проблемы пути на графиков -vertex (см, например , здесь ). 2 n ϵ ϵ > 0 F : { 0 , 1 } nN2nϵϵ>0F:{0,1}nN с т 0 1 т = м м 2 м п 1 / 3 т Рst01t=mm2mn1/3tF ssttmm

(Добавлено 14.11.2014): Поскольку Эмиль ответил на большую часть моего вопроса, и поскольку случай экспоненциальных порогов не видно, я теперь принимаю этот (очень хороший) ответ Эмиля.


Стасис
источник
Подождите ... экспоненциальный размер? Я думаю, что вы можете реализовать функцию среза в полиномиальном размере с логическими значениями, это просто формула (которая не может повторно использовать промежуточные результаты более одного раза), которая должна иметь экспоненциальный размер.
Zsbán Ambrus
@ Zsbán Ambrus: Есть максимум S a S цепей размераS, но, по крайней мере, 2 2 b n различныхk-слайсовых функций уже дляk=n / 2; а, б положительные константы. SaSS22bnkk=n/2
Стасис
Порог 2 и, в более общем смысле, пороги, ограниченные 2 n c2nc , можно эффективно смоделировать, выполнив вычисления в полукольце ( { 0 , , t } , min { x + y , t } , min { x y , t } ) . ({0,,t},min{x+y,t},min{xy,t})
Эмиль Йержабек поддерживает Монику
2
Вы получаете , схемы напрямую. Замените каждый узел c на t + 1 узлов c 0 , , c t,ct+1c0,,ct , где c i вычисляет логический предикат c i . (Вам не нужен c 0, поскольку он вычисляет константу 1 , но это упрощает приведенное ниже выражение.) В этом представлении + и можно смоделировать с помощью { , } цепей размера O ( tcicic01+{,}2 ) : например, если c = a + b , то c i = j + k i ( a jb k ) . O(t2)c=a+bci=j+ki(ajbk)
Эмиль Йержабек поддерживает Монику
1
@ Эмиль Йержабек: Очень мило! Я сейчас добавил замечание по этому поводу. На самом деле, возможно, стоит поставить этот комментарий в качестве ответа: случай порогового значения полинома также был не сразу ясен (по крайней мере, для меня).
Стасис

Ответы:

16

Ответ «да», если t = n O ( 1 )t=nO(1) . В более общем смысле, пороговую { + , } -цепь размера s с порогом t можно смоделировать с помощью { , } -цепи размера O ( t 2 s ) .{+,}st{,}O(t2s)

Во-первых, обратите внимание, что достаточно оценить схему в { 0 , , t } с усеченным сложением и умножением: в частности, если a , a t , то a + b , a + b t , и либо a b , a b t , или a b = a b ( = 0 ) .{0,,t}a,ata+b,a+btab,abtab=ab(=0)

Имея это в виду, мы можем смоделировать схему с булевой монотонной схемой, заменив каждый узел c узлами c 0 , , c t , где c i предназначен для вычисления предиката c i . (Нам нужен c 0 только для удобства обозначения, он вычисляет функцию константы 1. ) Если c является булевой входной переменной x , мы берем c 1 = x , c 2 = = c t = 0cc0,,ctcicic01cxc1=xc2==ct=0, Если c - строб сложения, скажем, c = a + b , мы реализуем его через c i = j , k t j + k i ( a jb k ) . Затворы умножения обрабатываются одинаково.cc=a+b

ci=j,ktj+ki(ajbk).

Это берет O ( t 3 ) вентилей на один вентиль оригинальной схемы. В качестве незначительной оптимизации мы можем уменьшить ее до O ( t 2 ) , поставив c tO(t3)O(t2)= j + k t ( a jb k ) , c i= С я + 1J + K = я ( JЬ к ) ,я < т , так что каждыйJбкиспользуетсякачестве входного сигнала только один изгряворот.

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