Complexidade exata de um problema em

Seja $x_i \in \{-1,0,+1\}$ para $i \in \{1,\ldots,n\}$ , com a promessa de que $x = \sum_{i=1}^n{x_i} \in \{0,1\}$ (onde a soma está acima ). Então, qual é a complexidade de determinar se ?$\mathbb{Z}$$x = 1$

Observe que trivialmente o problema está em porque iff x = 1 . A pergunta é: o problema está em \ mathsf {AC} ^ 0 ? Se sim, qual é o circuito que está testemunhando isso? Se não, como provar isso?$\cap_{m \geq 2}{\mathsf{AC}^0[m]}$ x = 1 A C$x \equiv 1\bmod{m}$$x = 1$$\mathsf{AC}^0$

Você pode usar o argumento de lema de comutação usual. Você não explicou como representa sua entrada em binário, mas, sob qualquer codificação razoável, a seguinte função é AC equivalente à sua função: (Assumimos que é par.) Após essas notas de aula , suponha que possa ser calculado por um circuito profundidade . Então uma restrição aleatória de deixa uma função da complexidade da árvore de decisão no máximo$^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$ com probabilidade de pelo menos . Um cálculo provavelmente mostrará que esta é outra instância de (em um tamanho de entrada menor) com probabilidade e, portanto, existe alguma restrição aleatória que gera uma instância de em entradas e uma função com complexidade constante da árvore de decisão, levando a uma contradição. O mesmo argumento deve gerar limites inferiores exponenciais.$1-1/(3n)$$f$$\Theta(1/\sqrt{n})$$f$$n^{1/2^d}$

Eu não acho que isso esteja em AC0 e posso mostrar um limite inferior para o problema de promessa relacionado de distinguir entre e , quando . Técnicas de Fourier semelhantes devem se aplicar ao seu problema, mas eu não verifiquei isso. Ou talvez haja uma redução simples.$\sum x_i = 0$$\sum x_i = 2$$x \in \{-1, 1\}^n$

Suponhamos que existe um tamanho profundidade d do circuito que calcula uma função f : { - 1 , 1 } n → { 0 , 1 } , tal que f ( x ) = Σ i x i sempre Σ i x i ∈ { 0 , 2 } . Porque para um x aleatório , a probabilidade de ∑ i x i = 0 é 2$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$, e para cada um dessesxexistemn/2coordenadas que alteram o valor def, a influência total deFéΩ(n1/2), que é aproximadamente o mesmo que maioria (porque você incluiu a maioria das entradas sensíveis da maioria). Por um teorema de Hastad (ver Colorraly 2.5 nasnotas deRyan O'Donnel), isso implica que$2^{-n} {n \choose n/2} \approx n^{-1/2}$$x$$n/2$$f$$f$$\Omega(n^{1/2})$

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