Kompleksitas sirkuit fungsi Mayoritas

Misalkan menjadi fungsi mayoritas, yaitu f ( x ) = 1 jika dan hanya jika β n i = 1 x i > n /$f: \{0,1\}^n \to \{0,1\}$$f(x) = 1$$\sum_{i = 1}^n x_i > n/2$ . Saya bertanya-tanya apakah ada bukti sederhana dari fakta berikut (dengan "sederhana" Maksud saya tidak mengandalkan metode probabilistik seperti yang dilakukan Valiant 84 atau pada jaringan sortir; lebih disukai memberikan konstruksi sirkuit yang eksplisit dan langsung):

dapat dikomputasi oleh sekelompok sirkuit dengankedalaman O ( log ( n ) ) , ukuran poli (n), di mana gerbang terdiri dari gerbang NOT, gerbang input-2 ATAU, dan gerbang input-2 DAN.$f$$O(\log(n))$

Jawaban Kaveh menyediakan jawaban lakukan pertanyaan seperti yang Anda telah menyatakan itu (dan ini adalah bukti biasa untuk menunjukkan bahwa terkandung dalam N C 1 ). Tetapi saya berpikir bahwa Anda mungkin sebenarnya bermaksud mengajukan pertanyaan yang sedikit berbeda. Yaitu untuk ukuran polinomial eksplisit$\mathsf{TC}^0$$\mathsf{NC}^1$ formula monoton untuk mayoritas.

Karena mayoritas adalah monoton kita tahu itu dapat dihitung dengan rumus monoton. Ada dua konstruksi yang dikenal sebagai rumus ukuran monoton polinomial, yaitu dua yang Anda sebutkan, konstruksi probabilistik Valiant dan konstruksi melalui jaringan sortasi. Sejauh yang saya tahu kami tidak memiliki konstruksi deterministik yang lebih sederhana daripada yang disediakan oleh jaringan sortir.

Terkait dengan ini juga berikut ini. Ternyata mayoritas yang dapat dihitung dengan formula yang terdiri dari hanya gerbang (dan tidak ada konstanta!). Konstruksi probabilistik Valiant dapat diadaptasi untuk memberikan formula kedalaman O ( log ( n ) ) seperti itu . Namun di sini kita tahu tidak ada konstruksi deterministik. Khususnya jaringan penyortiran tidak cocok untuk ini (alasan teknis: mereka akan menyediakan semua fungsi ambang batas dan hanya fungsi mayoritas yang dapat dihitung sama sekali oleh M A J 3 Protokol Multipartai yang Efisien melalui Rumus Ambang Batas Kedalaman Log)$\mathsf{MAJ}_3$$O(\log(n))$$\mathsf{MAJ}_3$ gerbang). Namun ada kemajuan terbaru pada pertanyaan ini yang diberikan di koran oleh Cohen et al. Di sini, rumus-rumus semacam itu dibangun berdasarkan asumsi kompleksitas-teoretis atau kriptografis.

Komputasi gerbang ambang batas terbatas ( ) pada dasarnya mengurutkan bit input.$\sum_i x_i \geq k$

Jika Anda dapat mengurutkan bit maka mudah untuk membandingkan hasilnya dengan dan menghitung ambang batas terbatas.$k$

Di sisi lain, asumsikan bahwa kita memiliki sirkuit untuk menghitung ambang batas terbatas. Kita dapat melakukan pencarian paralel untuk menemukan jumlah yang ada di input dan menampilkan daftar yang diurutkan.

Ini menjaga kedalaman sirkuit. Jadi jika Anda datang dengan sirkuit untuk menghitung ambang batas terbatas maka akan memberikan kedalaman O ( lg n ) sirkuit penyortiran. Jadi jika kita datang dengan argumen sederhana untuk menunjukkan mayoritas dalam N C 1 Anda telah menemukan rangkaian sortasi kedalaman- O ( lg n ) sederhana (selain yang didasarkan pada jaringan sortir AKS).$\mathsf{NC^1}$$O(\lg n)$$\mathsf{NC^1}$$O(\lg n)$

Perhatikan bahwa mudah untuk menerapkan ambang terbatas menggunakan mayoritas dengan menambahkan input 1 dan 0 baru ke gerbang mayoritas.

Sebelumnya jawaban ini menyatakan bahwa hal itu dapat dilakukan dengan menggunakan divide and conquer dan fakta bahwa penambahan biner ada dalam . Itu hanya menunjukkan bahwa mayoritas berada di A C 1 dan N C 2 karena kita memiliki gerbang fan-in yang tidak terbatas dalam penambahan biner jika kita melakukannya secara langsung. Namun itu bisa dilakukan dengan sedikit lebih banyak pekerjaan.$\mathsf{AC^0}$$\mathsf{AC^1}$$\mathsf{NC^2}$

Kita harus menggunakan trik yang disebut tiga-untuk-dua agar tetap dalam kedalaman .$O(\lg n)$

$a,b,c$$x,y$$a+b+c = x+y$

$O(1)$

Lihat bagian 4 dan latihan 4 dalam

• David Mix Barrington dan Alexis Maciel, " Kursus Lanjutan tentang Kompleksitas Komputasi ", kuliah 6, IAS / PCMI, 2000.

Bukti (karena Miller dan Preparata, 1975) bahwa setiap fungsi simetris dapat dihitung oleh sirkuit lebih dari {DAN, ATAU, TIDAK} dalam kedalaman logaritmik dapat ditemukan, misalnya, dalam Kompleksitas Fungsi Boolean oleh Ingo Wegener (Teorema 4.1, halaman 76). Sirkuit yang sesuai memiliki ukuran linier. Dan karena kedalamannya adalah logaritmik, ia dapat diubah menjadi rumus ukuran polinomial. Buktinya sederhana dan memberikan konstruksi eksplisit. Pada dasarnya, ini menunjukkan bagaimana menghitung representasi biner dari jumlah$n$ bit input dalam kedalaman logaritmik (memiliki jumlah ini mudah untuk menghitung mayoritas).

An alternative proof is given by Brodal and Husfeldt: A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth. Again, the proof is elementary and provides an explicit construction.