Pode-se provar

Resultado 1: O teorema de Linial-Mansour-Nisan diz que o peso quádruplo das funções calculadas pelos circuitos está concentrado nos subconjuntos de tamanho pequeno com alta probabilidade. $\mathsf{AC}^0$

Resultado 2: O tem seu peso fourier concentrado no coeficiente do grau . $\mathsf{PARITY}$ $n$

Pergunta: Existe uma maneira de provar (se possível) $\mathsf{PARITY}$ não é computável por circuitos $\mathsf{AC}^0$ via / usando os resultados 1 e 2?

cc.complexity-theory circuit-complexity boolean-functions fourier-analysis Stattrav
fonte

Não é uma aplicação óbvia do teorema de Linial-Mansour-Nisan? Como o teorema do LMN é provado (em particular, se é provado por argumento probabilístico ou não) é irrelevante.

Tsuyoshi Ito

ao mesmo tempo, o teorema de Linial-Mansour-Nisan não é provado assumindo o teorema de Hastad? Parece-me como um cão perseguindo o próprio rabo ...

Alessandro Cosentino

É assim que o limite inferior do tamanho de um circuito AC0 que se aproxima da paridade é derivado nas notas de Ryan O'Donnell . Veja o corolário 32.

Sasho Nikolov

Penso que a pergunta mais interessante está no seu comentário: todas as funções cujo espectro de Fourier está concentrado em coeficientes de baixo nível computáveis por circuitos AC0 de tamanho pequeno.

Sasho Nikolov 20/09/2012

@ Strattav Então você pode fazer essa pergunta.

Tyson Williams

Respostas:

O teorema do LMN mostra que, se f é uma função booleana computável por um circuito do tamanho M, $(f:\{-1,1\}^n \rightarrow \{-1,1\})$ $\text{AC}^0$

\sum_{S : | S | > k} \hat{f} (S)^{2} \leq 2^{- Ω (k / (\log M)^{d - 1})}

$\sum_{S:|S|> k} \hat f(S)^{2} \leq 2^{-\Omega(k/(\log M)^{d-1})}$

$\Rightarrow \hat f([n])^{2} \leq 2^{-\Omega(n/(\log M)^{d-1})}$

$\Rightarrow |\hat f([n])| \leq 2^{-\Omega(n/(\log M)^{d-1})}$

nada mais é do que a correlação de f com a função de paridade . Deixe ser a fracção de entradas onde difere da . $|\hat f([n])|$ $(\prod_{i = 1}^{n}x_i)$ $\delta$ $f$ $PARITY$

\begin{aligned} 1 - 2 δ \leq | 1 - 2 δ | & = | \hat{f} ([n]) | \leq 2^{- Ω (n / (\log M)^{d - 1})} \\ \Rightarrow δ & \geq 1 - 2^{- Ω (n / (\log M)^{d - 1})} \end{aligned}

$\begin{align} 1 -2 \delta \leq |1 - 2\delta| &= |\hat f([n])| \leq 2^{-\Omega(n/(\log M)^{d-1})}\\ \Rightarrow \delta &\geq 1 - 2^{-\Omega(n/(\log M)^{d-1})} \end{align}$

So, if M is $poly(n)$ , for $f$ to be equal to $PARITY$ ,

\begin{aligned} δ & \leq \frac{1}{2^{n}} \\ \Rightarrow 2^{n} & \geq 2^{(c n / (\log M)^{d - 1})} \\ \Rightarrow (\log M)^{d - 1} & \geq (c - 1) n \\ \Rightarrow M & \geq 2^{Ω (n^{1 / d - 1})} \end{aligned}

$\begin{align} \delta &\leq \frac{1}{2^n}\\ \Rightarrow 2^n &\geq 2^{(cn/(\log M)^{d-1})}\\ \Rightarrow (\log M)^{d-1} &\geq (c-1)n \\ \Rightarrow M &\geq 2^{\Omega (n^{1/d-1})} \end{align}$

So, LMN theorem not only proves that $PARITY$ cannot be computed by $AC^{0}$ circuits, it also shows that $PARITY$ has low correlation with $AC^{0}$ circuits.

Tulasi
fonte