Complejidad exacta de un problema en

Deje para , con la promesa de que (donde la suma ha terminado ). Entonces, ¿cuál es la complejidad de determinar si ?$x_i \in \{-1,0,+1\}$$i \in \{1,\ldots,n\}$$x = \sum_{i=1}^n{x_i} \in \{0,1\}$$\mathbb{Z}$$x = 1$

Observe que trivialmente el problema radica en porque iff . La pregunta es: ¿el problema radica en ? Si es así, ¿cuál es el circuito testigo de esto? Si no, ¿cómo se prueba esto?$\cap_{m \geq 2}{\mathsf{AC}^0[m]}$$x \equiv 1\bmod{m}$$x = 1$$\mathsf{AC}^0$

Puede usar el argumento de lema de cambio habitual. No ha explicado cómo representa su entrada en binario, pero bajo cualquier codificación razonable, la siguiente función es AC equivalente a su función: (Suponemos que es par.) Siguiendo estas notas de clase , suponga que puede calcularse por un circuito de profundidad de tamaño . Entonces, una restricción aleatoria de entradas deja como máximo una función de la complejidad del árbol de decisión 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 , ? de otra manera. $^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^b$$n - n^{1/2^d}$$2^d(b+1)+1$ con probabilidad de al menos . Un cálculo probablemente mostrará que esta es otra instancia de (en un tamaño de entrada más pequeño) con probabilidad , por lo que hay alguna restricción aleatoria que produce una instancia de en entradas y una función con complejidad constante del árbol de decisión, lo que lleva a una contradicción. El mismo argumento debería producir límites inferiores exponenciales.$1-1/(3n)$$f$fn 1 / 2 $\Theta(1/\sqrt{n})$$f$$n^{1/2^d}$

No creo que esto esté en AC0 y puedo mostrar un límite inferior para el problema de promesa relacionado de distinguir entre y , cuando . Técnicas similares de Fourier deberían aplicarse a su problema, pero no lo he verificado. O tal vez hay una simple reducción.$\sum x_i = 0$$\sum x_i = 2$$x \in \{-1, 1\}^n$

Supongamos que hay un tamaño profundidad circuito que calcula una función tal que siempre que . Porque para una aleatoria , la probabilidad de que sea , y para cada una de esas hay coordenadas que cambian el valor de , la influencia total de es$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$xn/2ffΩ(n1/2$2^{-n} {n \choose n/2} \approx n^{-1/2}$$x$$n/2$$f$$f$$\Omega(n^{1/2})$, que es aproximadamente lo mismo que mayoría (porque incluyó la mayoría de las entradas sensibles de la mayoría). Según un teorema de Hastad (ver Colorraly 2.5 en las notas de Ryan O'Donnel ), esto implica que

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