Complexité exacte d'un problème en

Soit $x_i \in \{-1,0,+1\}$ pour $i \in \{1,\ldots,n\}$ , avec la promesse que $x = \sum_{i=1}^n{x_i} \in \{0,1\}$ (où la somme est supérieure à $\mathbb{Z}$ ). Quelle est alors la complexité de déterminer si $x = 1$ ?

$\cap_{m \geq 2}{\mathsf{AC}^0[m]}$ x = 1 A C$x \equiv 1\bmod{m}$$x = 1$$\mathsf{AC}^0$

Vous pouvez utiliser l'argument habituel du lemme de commutation. Vous n'avez pas expliqué comment vous représentez votre entrée en binaire, mais sous tout encodage raisonnable, la fonction suivante est équivalente à AC à votre fonction: (Nous supposons que est pair.) Après ces notes de cours , supposons que peut être calculé par un circuit de profondeur de taille . Ensuite, une restriction aléatoire de entrées laisse une fonction de la complexité de l'arbre de décision au plus f ( x 1 , … , x n ) = { 0 si  x 1 - x 2 + x 3 - x 4 + ⋯ - x n = 0 , 1 si  x 1 - x 2 + x 3 - x 4 + ⋯ - x n = 1 , ? autrement. n f $^0$

$$f(x_1,\ldots,x_n) = \begin{cases} 0 & \text{if }x_1 - x_2 + x_3 - x_4 + \cdots - x_n = 0, \\ 1 & \text{if }x_1 - x_2 + x_3 - x_4 + \cdots - x_n = 1, \\ ? & \text{otherwise.} \end{cases}$$ $n$$f$$d$ n - n 1 / 2 d 2 d ( b + 1 ) + 1 1 - 1 / ( 3 n ) f Θ ( 1 / $n^b$$n - n^{1/2^d}$$2^d(b+1)+1$ avec une probabilité d'au moins . Un calcul montrera probablement qu'il s'agit d'une autre instance de (sur une taille d'entrée plus petite) avec la probabilité , et donc il y a une restriction aléatoire qui donne à la fois une instance de sur entrées et une fonction à complexité d'arbre de décision constante, conduisant à une contradiction. Le même argument devrait produire des bornes inférieures exponentielles.$1-1/(3n)$$f$fn une / 2 $\Theta(1/\sqrt{n})$$f$$n^{1/2^d}$

Je ne pense pas que ce soit dans AC0 et je peux montrer une limite inférieure pour le problème de promesse connexe de distinguer entre et , lorsque . Des techniques de Fourier similaires devraient s'appliquer à votre problème, mais je ne l'ai pas vérifié. Ou peut-être qu'il y a une réduction simple.∑ x i = 2 x ∈ { - 1 , 1 } $\sum x_i = 0$$\sum x_i = 2$$x \in \{-1, 1\}^n$

Supposons qu'il existe un circuit de profondeur taille qui calcule une fonction telle que chaque fois que . Parce que pour un aléatoire , la probabilité que est , et pour chacun de ces il y a coordonnées qui modifient la valeur de , l'influence totale de estd f : { - 1 , 1 } n → { 0 , 1 } f ( x ) = ∑ i x i ∑ i x i ∈ { 0 , 2 } x ∑ i x i = 0 2 - n ($s$$d$$f: \{-1, 1\}^n \rightarrow \{0, 1\}$$f(x) = \sum_i x_i$$\sum_i x_i \in \{0,2\}$$x$$\sum_i x_i = 0$$2^{-n} {n \choose n/2} \approx n^{-1/2}$$x$f f Ω ( n 1 / 2$n/2$$f$$f$$\Omega(n^{1/2})$, qui est à peu près la même chose que la majorité (car vous avez inclus la plupart des entrées sensibles de la majorité). Selon un théorème de Hastad (voir Colorraly 2.5 dans les notes de Ryan O'Donnel ), cela implique que

$$s \geq 2^{\Omega(n^{1/(2d-2)})}.$$