Dokładna złożoność problemu w

Pozwolić $x_i \in \{-1,0,+1\}$ dla $i \in \{1,\ldots,n\}$, z obietnicą, że $x = \sum_{i=1}^n{x_i} \in \{0,1\}$ (gdzie suma się skończyła $\mathbb{Z}$). Jaka jest złożoność ustalenia, czy$x = 1$?

Zauważ, że w trywialny sposób leży problem $\cap_{m \geq 2}{\mathsf{AC}^0[m]}$ ponieważ $x \equiv 1\bmod{m}$iff . Pytanie brzmi: czy problem leży w ? Jeśli tak, to co świadczy o tym obwód? Jeśli nie, to jak to udowodnić?$x = 1$$\mathsf{AC}^0$

Możesz użyć zwykłego argumentu lematu przełączającego. Nie wyjaśniłeś, w jaki sposób reprezentujesz swoje dane wejściowe w formacie binarnym, ale przy jakimkolwiek rozsądnym kodowaniu następująca funkcja jest AC równoważna twojej funkcji: (Zakładamy, że jest parzyste). Po tych notatkach z wykładów przypuśćmy, że można obliczyć z obwodu głębokości o rozmiarze . Następnie losowe ograniczenie danych wejściowych pozostawia co najwyżej funkcję złożoności drzewa decyzyjnego$^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$ z prawdopodobieństwem co najmniej . Obliczenia prawdopodobnie pokażą, że jest to kolejna instancja (przy mniejszym rozmiarze wejściowym) z prawdopodobieństwem , a więc istnieje pewne losowe ograniczenie, które daje zarówno instancję na Wejścia i funkcja o stałej złożoności drzewa decyzyjnego, co prowadzi do sprzeczności. Ten sam argument powinien dawać wykładnicze dolne granice.$1-1/(3n)$$f$$\Theta(1/\sqrt{n})$$f$$n^{1/2^d}$

Nie sądzę, że jest to w AC0 i mogę pokazać dolną granicę dla pokrewnego problemu obietnicy rozróżnienia między a , gdy . Podobne techniki Fouriera powinny mieć zastosowanie do twojego problemu, ale tego nie zweryfikowałem. A może jest prosta redukcja.$\sum x_i = 0$$\sum x_i = 2$$x \in \{-1, 1\}^n$

Załóżmy, że jest rozmiarem głębokość obwód, który oblicza się funkcję tak, że gdy . Ponieważ dla losowego prawdopodobieństwo, że wynosi , a dla każdego takiego jest współrzędne zmieniające wartość , całkowity wpływ wynosi$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$$n/2$$f$$f$$\Omega(n^{1/2})$, czyli mniej więcej tyle samo, co większość (ponieważ uwzględniono większość wrażliwych danych większości). Twierdzenie Hastada (patrz Colorraly 2.5 w notatkach Ryana O'Donnela ) oznacza, że

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