Sirkuit kedalaman-2 dengan gerbang OR dan MOD tidak universal?

Sudah diketahui secara umum bahwa setiap fungsi boolean $f:\{0,1\}^n\to \{0,1\}$ dapat direalisasikan menggunakan sirkuit boolean dengan kedalaman 2 (atas variabel, negasi dan nilai konstannya) yang berisi gerbang AND di yang pertama tingkat dan satu gerbang OR tunggal di tingkat atas; ini hanyalah representasi DNF dari $f$ .

Tipe lain dari pintu gerbang yang sangat menarik dalam kompleksitas sirkuit adalah $MOD_m$ gerbang. Definisi yang biasa adalah sebagai berikut:

{M. HAI D}_{m} (x_{1}, ..., x_{k}) = {\begin{cases} 1 & jika \sum x_{saya} \equiv 0 \mod m \\ 0 & jika \sum x_{saya} ≢ 0 \mod m \end{cases}

$\mathrm{MOD}_m(x_1,\dots,x_k)=\cases{ 1 & if $\sum x_i \equiv 0 \mod m$ \\ 0 & if $\sum x_i \not\equiv 0 \mod m$ \\ }$

Gerbang ini terkadang memiliki kekuatan yang mengejutkan; misalnya, fungsi boolean apa pun dapat diwakili oleh sirkuit kedalaman-2 yang hanya memiliki gerbang $\mathrm{MOD}_6$ (ini adalah cerita rakyat tapi saya bisa menguraikan apakah seseorang tertarik).

Namun, cerita rakyat lainnya adalah bahwa sirkuit dengan gerbang OR tunggal di bagian atas dan gerbang $\mathrm{MOD}_m$ di lapisan bawah (dengan $m$ diperbaiki sekali dan untuk semua, dan khususnya sama untuk semua gerbang) tidak universal, yaitu untuk setiap nilai $m$ , ada fungsi boolean yang tidak dapat dihitung oleh sirkuit $\mathrm{OR} \circ \mathrm{MOD}_m$ .

Saya mencari bukti untuk klaim ini, atau setidaknya beberapa arahan.

complexity-theory logic circuits Gadi A
sumber

Pada paragraf pertama, Anda TIDAK perlu gerbang atau Anda harus mengatakan "setiap fungsi Boolean monoton ."

Tsuyoshi Ito

Anda benar; asumsi yang biasa adalah bahwa Anda memiliki input variabel, negasinya dan juga nilai arbitrer (penting untuk modgates). Saya akan menulis ini secara eksplisit.

Gadi A

Saya kira , jumlah variabel input, berbeda dari , modulus?

n

$n$

n

$n$

Kristoffer Arnsfelt Hansen

Ya, maaf soal itu.

Gadi A

Saya tertarik dengan ini. Apakah Anda tahu referensi untuk fakta folkloric pertama? Saya bertanya-tanya, jika di kelas sirkuit terakhir Anda hanya mengizinkan satu ATAU, berapa banyak yang Anda izinkan di sirkuit sebelumnya?

Juan Bermejo Vega

Fungsi Boolean AND tidak dapat dihitung. Misalkan sebenarnya fungsi AND dikomputasi oleh sirkuit . Maka itu berarti bahwa salah satu dari subcircuits MOD harus menghitung kemudian fungsi AND, yang tidak mungkin. $\text{OR} \circ \text{MOD}$

Kristoffer Arnsfelt Hansen
sumber

Tidak, dia benar. Asumsi implisit di sini adalah bahwa n adalah konstan dan kita harus dapat menangani sejumlah besar input sewenang-wenang dengan gerbang mod_n.

Gadi A

@GadiA Ah, baiklah. Ini tidak jelas dalam pertanyaan Anda, setidaknya untuk orang yang tidak terbiasa dengan bidang ini. Saya telah membuat suntingan kecil yang harus menjelaskan hal ini.

Gilles 'SANGAT berhenti menjadi jahat'

Ya, pertanyaan saya diungkapkan dengan sangat buruk, maaf.

Gadi A

@Gilles Bisakah Anda jelaskan penggemar apa yang kami pertimbangkan di sini? Masalahnya bagi saya adalah saya tidak bisa melihat mengapa subcircuit dari MOD tidak bisa menghitung AND? Berapa banyak input yang memiliki MOD ini dan DAN ini?

Sirkuit kedalaman-2 dengan gerbang OR dan MOD tidak universal?

Jawaban: