Сколько отрицаний нам нужно для вычисления монотонных функций?

14

Разборов доказал, что соответствие монотонной функции отсутствует в мП . Но можем ли мы вычислить соответствие, используя схему полиномиального размера с несколькими отрицаниями? Существует ли P / поли схема с O(nϵ) отрицаниями, которая вычисляет совпадение? Каков компромисс между числом отрицаний и размером для сопоставления?

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

Ответы:

21

Марков доказал, что любая функция из входов может быть вычислена только с log ( n + 1 ) отрицаниями. Эффективная конструктивная версия была описана Фишером. Смотрите также экспозицию результата из блога GLL .nlog(n+1)

Точнее:

Теорема: Предположим, что вычисляется схемой C с g затворами, а затем вычисляется схемой C с 2 g + O ( n 2 log 2 n ) Гейтс и log ( n + 1 ) отрицания.f:{0,1}n{0,1}mCgC2g+O(n2log2n)log(n+1)

Основная идея состоит в том, чтобы добавить для каждого провода в C провод parellel w в C ∗, который всегда несет дополнение w . Базовый случай для входных проводов: Фишер описывает , как построить схему инверсии I ( х ) = ¯ х с О ( п 2 лога 2 л ) ворота и только лог ( п + 1 ) отрицания. Для логических элементов И цепи С , мы можем дополнитьwCwCwI(x)=x¯O(n2log2n)log(n+1)C с a = b c , а также для вентилей OR. Ворота NOT в C ничего не стоят, мы просто поменяемся ролями w и w ' ниже по потоку от шлюза NOT. Таким образом, вся схема, кроме подсхемы инвертора, является монотонной.a=bca=bcCww

А.А. Марков. Об инверсионной сложности системы функций. J. ACM , 5 (4): 331–334, 1958.

М. Дж. Фишер. Сложность сетей с ограничением отрицания - краткий обзор. В теории автоматов и формальных языков , 71–82, 1975

mikero
источник
Это схема P / поли?
Аноним
2
Да, размер схемы изменяется от до 2 g + O ( n 2 log 2 n ), где n - количество входов. Я расширил ответ, чтобы включить более точное изложение результата и сделать его более автономным. g2g+O(n2log2n)n
Микеро
4
И некоторые явные (многократные) монотонные функции в P / poly требуют, чтобы по крайней мере отрицания оставались в P / poly. lognO(loglogn)
Стасис
2
Для этой линии вопросов (сила отрицаний в схемах / формулах / и т. Д.) Может иметь отношение следующее: eccc.hpi-web.de/report/2014/144 , eprint.iacr.org/2014/902 и eccc. hpi-web.de/report/2015/026 .
Клемент С.
2
достаточно дляdimacs.rutgers.edu/TechnicalReports/abstracts/1995/95-31.html. 2g+O(nlogn)
Эмиль Йержабек поддерживает Монику
1

Как вычислить инверсию бит, используя n отрицаний2n1n

Пусть биты отсортированы в порядке убывания, т.е. i < j означает x ix j . Этого можно достичь с помощью монотонной сортировочной сети, такой как сортировочная сеть Айтай-Комлос-Семереди.x0,,x2n1i<jxixj

Определим схему инверсии для битов I n ( x ) индуктивно: для базового случая имеем n = 1 и I 1 0 ( x ) : = ¬ x 0 . Пусть m = 2 n - 1 . Мы уменьшаем I n (для 2 m + 1 ) бит до одного I n - 1 вентиля (для m2n1In(x)n=1I01(x):=¬x0m=2n1In2m+1In1m¬xm. For i<m let yi:=(xi¬xm)xm+i. We use In1 to invert y. Now we can define In as follows:

Iin:={Iin1(y)¬xmi<m¬xmi=mIin1(y)¬xmi<m

It is easy to verify this inverts x by considering the possible values of xn and using the fact that x is decreasing.

From Michael J. Fischer, The complexity of negation-limited networks - a brief survey, 1975.

Anonymous
источник