Kompleksitas yang tepat dari masalah dalam

Biarkan untuk , dengan janji bahwa (di mana jumlahnya lebih dari ). Lalu apa kompleksitas penentuan jika ?$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$

Perhatikan bahwa secara sepele masalahnya terletak pada karena iff x = 1 . Pertanyaannya adalah: apakah masalahnya ada pada \ mathsf {AC} ^ 0 ? Jika demikian, apa sirkuit yang menyaksikan ini? Jika tidak, bagaimana orang membuktikan ini?$\cap_{m \geq 2}{\mathsf{AC}^0[m]}$$x \equiv 1\bmod{m}$A C$x = 1$$\mathsf{AC}^0$

Anda dapat menggunakan argumen lemma switching yang biasa. Anda belum menjelaskan bagaimana Anda merepresentasikan input Anda dalam biner, tetapi di bawah penyandian yang masuk akal, fungsi berikut ini adalah AC sama dengan fungsi Anda: (Kami berasumsi bahwa adalah genap.) Mengikuti catatan kuliah ini , anggaplah bahwa dapat dihitung dengan kedalaman rangkaian ukuran . Kemudian pembatasan acak dari meninggalkan fungsi kompleksitas pohon keputusan f ( x 1 , … , x n ) = { 0 jika  x 1 - x 2 + x 3 - x 4 + ⋯ - x n = 0 , 1 jika  x 1 - x 2 + x 3 - x 4 + ⋯ - x n = 1 , ? jika tidak. 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^b$$n - n^{1/2^d}$$2^d(b+1)+1$ dengan probabilitas setidaknya . Perhitungan mungkin akan menunjukkan bahwa ini adalah contoh lain dari (pada ukuran input yang lebih kecil) dengan probabilitas , dan ada beberapa pembatasan acak yang menghasilkan kedua instance dari pada input dan fungsi dengan kompleksitas pohon keputusan konstan, yang mengarah ke kontradiksi. Argumen yang sama harus menghasilkan batas bawah eksponensial.$1-1/(3n)$$f$$\Theta(1/\sqrt{n})$$f$$n^{1/2^d}$

Saya tidak berpikir ini ada di AC0 dan saya bisa menunjukkan batas bawah untuk masalah janji terkait yang membedakan antara dan , ketika . Teknik Fourier yang serupa harus diterapkan untuk masalah Anda, tetapi saya belum memverifikasi itu. Atau mungkin ada pengurangan sederhana.$\sum x_i = 0$$\sum x_i = 2$$x \in \{-1, 1\}^n$

Misalkan ada ukuran kedalaman sirkuit yang menghitung fungsi sehingga setiap kali . Karena untuk acak , probabilitas bahwa adalah , dan untuk setiap ada koordinat yang mengubah nilai , pengaruh total adalah$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})$, yang kira-kira sama dengan mayoritas (karena Anda memasukkan sebagian besar input sensitif mayoritas). Dengan teorema Hastad (lihat Colorraly 2.5 dalam catatan Ryan O'Donnel ), ini menyiratkan hal itu

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