Я читаю приложение о АССЕ нижних границах для NEXP в Arora и Барак вычислительной сложности книги. http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf Одна из ключевых лемм - это преобразование из цепей в полилинейные полиномы над целыми числами с полилогарифмической степенью и квазиполиномиальными коэффициентами или эквивалентно , класс цепей S Y M + , который является классом глубинных двух цепей с квазиполиномиальным числом логических элементов И на его нижнем уровне с полилогарифмическим разветвлением и симметричным затвором на верхнем уровне.
В приложении к учебнику это преобразование состоит из трех этапов, при условии, что набор ворот состоит из ИЛИ, mod , mod 3 и константы 1 . Первым шагом является уменьшение разветвления вентилей OR до полилогарифмического порядка.
Использование Валиант-Вазирани Isolation лемму, авторы получаем , что дан логический элемент ИЛИ над входов вида вывода R ( х 1 , . . . , Х 2 K ) , если мы выбираем час быть попарно независимы хэш - функция от [ 2 k ] до { 0 , 1 } , то для любого ненулевого x ∈ { 0 , 1 } 2 k с вероятностью не менее 1 / ( будет иметь место, что Σ i : h ( i ) = 1 x i mod 2 .
Не является ли вероятность , по крайней мере 1 / 2 ? Представляется , что 1 / 10 K является слабой нижней гранью.
Второй шаг - переход к арифметическим воротам и опускание умножений вниз. На этом этапе мы преобразуем логические схемы с заданной двоичной входной строкой в арифметическую схему с целочисленным входом.
При этом они отмечают , что заменяется на 1 - х 1 х 2 ⋯ х к и М О Д р ( х 1 , . . . , Х к ) заменяется ( Σ я = 1 , . . . , к й я ) р - с использованием маленькой теоремы Ферма.
Почему эта замена дает эквивалентную цепь ?
Ответы:
На самом деле ответ - нет. (Было бы , что имеет место с вероятностью по крайней мере 1 / 2 - е , если мы работали с й -biased хэш семейством, и , действительно , используя ε -biased хэша Функция дает возможность улучшить параметры построения. Но парная независимость не обязательно ε- смещена.)Σi:h(i)=1ximod 2=1 1/2−ε ε ε ε
Кажется, они пропустили еще один шаг здесь. Чтобы применить Valiant-Vazirani напрямую, вам также нужно будет случайным образом выбрать диапазон хэш-функции. Вместо того, чтобы выбирать случайные попарно независимые , кажется, вы должны выбрать случайные ℓ ∈ { 2 , … , k + 1 }, а затем выбрать случайные попарно независимые h : [ 2 k ] → { 0 , 1 } ℓh:[2k]→{0,1} ℓ∈{2,…,k+1} h:[2k]→{0,1}ℓ . (Здесь я намеренно использую высказывание Арора-Барака о Валиант-Вазирани, найденное на стр. 354.) будет числом x i = 1 . Валиант-Вазирани говорит, что если вы выбрали ℓ так , что 2 ℓ - 2 ≤ s ≤ 2 ℓ - 1 , то вероятность того, что Σ i : h ( i ) = 1 x i = 1 (по целым числам!), Равна по крайней мере 1 / 8 .s xi=1 ℓ 2ℓ−2≤s≤2ℓ−1 Σi:h(i)=1xi=1 1/8
A SYM of AND (i.e, SYM+) circuit of sizeK is essentially equivalent to having a multivariate polynomial h:{0,1}n→{0,…,K} with at most K monomials, a lookup table g:{0,…,K}→{0,1} , and computing g(h(x1,…,xn)) . (For instance, a proof can be found in Beigel-Tarui.) The intuition is that each monomial in f is an AND gate, and g is the SYM gate. I say "essentially equivalent" because the multilinear polynomial h could also have negative coefficients for some terms, and negative coefficents are not obviously implementable in SYM of AND. But I claim (and Beigel and Tarui claim) that this is not a problem. Think about it :)
источник