Bagaimana kecil dapat menjadi sirkuit boolean berlapis untuk fungsi dengan kompleksitas sirkuit

Pertimbangkan fungsi dihitung oleh sirkuit boolean dengan input ukuran atas dasar (dengan indegree 2 untuk gates). $f$ $C$ $n$ $s(n) = \mathsf{poly}(n)$ $\{\mathsf{XOR},\mathsf{AND},\mathsf{NOT}\}$ $\mathsf{XOR},\mathsf{AND}$

Sirkuit boolean berlapis jika dapat disusun menjadi lapisan ( menjadi kedalaman rangkaian) gerbang sedemikian rupa sehingga setiap tepi antara dua gerbang menghubungkan lapisan yang berdekatan. $d$ $d$

Mengingat bahwa memiliki sirkuit boolean dengan ukuran , apa yang dapat kita katakan tentang ukuran komputasi sirkuit berlapis ? Ada batas atas sepele: dengan menambahkan node dummy ke pada setiap layer yang dilintasi oleh tepi, kita mendapatkan sirkuit ukuran layered paling banyak . Tapi kita bisa mendapatkan yang lebih baik secara umum (misalnya , atau ), atau untuk kelas yang menarik dari sirkuit? $f$ $s$ $f$ $C$ $O(s^2)$ $O(s\cdot \log s)$ $O(s)$

Latar Belakang. Pertanyaan ini berasal dari hasil terbaru dalam kriptografi yang menunjukkan bagaimana cara menghitung sirkuit boolean dengan ukuran dengan komunikasi (misalnya atau ; Saya mencoba memahami bagaimana membatasi pembatasan ini untuk sirkuit boolean berlapis dalam praktiknya, baik untuk sirkuit umum atau untuk sirkuit "alami". Namun, saya belum menemukan banyak tentang sirkuit berlapis dalam literatur; petunjuk yang sesuai juga akan disambut. $s$ $o(s)$ $s/\log s$ $s/\log\log s)$

circuit-complexity circuits Geoffroy Couteau
sumber

Berikut adalah contoh sirkuit yang tampaknya sulit dikonversi ke sirkuit berlapis tanpa ukuran yang signifikan. Tentukan

menjadi beberapa fungsi yang dapat dihitung dalam ukuran

. Tentukan

f : {0, 1}^{n - 1} \to {0, 1}

$f:\{0,1\}^{n-1} \to \{0,1\}$

u

$u$

, dan membiarkan

menjadi

iterasi dari

. Kemudian

memiliki ukuran

. Tampaknya sulit untuk membangun sebuah sirkuit berlapis dengan ukuran kurang dari

. Jadi, jika

, mungkin kita harus mengharapkan celah antara ukuran sirkuit vs ukuran sirkuit berlapis. Bukan bukti, hanya contoh sugestif untuk mungkin mendorong intuisi.

g (x_{1}, \dots, x_{n}) = (x_{2}, \dots, x_{n}, x_{1} \oplus f (x_{2}, \dots, x_{n}))

$g(x_1,\dots,x_n) = (x_2,\dots,x_n,x_1 \oplus f(x_2,\dots,x_n))$

C

$C$

t

$t$

g

$g$

C

$C$

O (t u)

$O(tu)$

Θ (n t)

$\Theta(nt)$

u = o (n)

$u=o(n)$

Sejauh yang saya ingat, untuk sirkuit berlapis batas bawah paling dikenal adalah dari bentuk

. Hal ini sangat mudah untuk membuktikan untuk

-to-

fungsi. Ambil, misalnya, peta linier

mana

memiliki nol pada diagonal utama saja. Maka itu harus memiliki setidaknya

gerbang di setiap lapisan dan jumlah lapisan setidaknya

. Perhatikan bahwa fungsi ini dapat dengan mudah dihitung oleh sirkuit reguler ukuran

Ω (n \log n)

$\Omega(n \log n)$

n

$n$

n

$n$

A x

$Ax$

A \in {0, 1}^{n \times n}

$A \in \{0,1\}^{n \times n}$

n

$n$

\log_{2} n

$\log_2 n$

. Untuk fungsi single-output, juga dimungkinkan untuk membuktikan batas bawah yang sama, tapi saya tidak ingat argumennya.

O (n)

$O(n)$

Alexander S. Kulikov

Terima kasih banyak atas komentarnya. @ AlexanderS.Kulikov, apakah cerita rakyat argumen Anda, atau apakah Anda memiliki beberapa pointer untuk bekerja pada sirkuit berlapis? The

masuk akal - saya akan sangat terkejut oleh sesuatu yang lebih kecil - tetapi

hanya diketahui atas terikat?

Ω (n \log n)

$\Omega(n \log n)$

O (n^{2})

$O(n^2)$

Geoffroy Couteau

Saya kira itu adalah cerita rakyat, ya. Saya tidak yakin mendapatkan pertanyaan tentang batas atas

. Anda mungkin ingin melihat makalah berikut: cs.utexas.edu/~panni/sizedepth.pdf

O (n^{2})

$O(n^2)$

Alexander S. Kulikov

Saya pikir kita tidak tahu transformasi yang lebih baik daripada

secara umum. Perhatikan bahwa sirkuit ukuran

dan kedalaman

dapat diubah menjadi sirkuit ukuran berlapis paling banyak

. (Yang dalam kasus terburuk memberi kita sirkuit ukuran

.) Saya hanya ingin menunjukkan bahwa jika kita bisa membuktikan batas bawah

pada ukuran sirkuit yang berlapis, ini akan memberi kita batas bawah super-linear pada ukuran sirkuit log-depth untuk fungsi ini. Pertanyaan ini tetap terbuka selama lebih dari 40 tahun.

O (s^{2})

$O(s^2)$

s

$s$

d

$d$

d s

$ds$

O (s^{2})

$O(s^2)$

ω (n \log n)

$\omega(n\log{n})$

Alex Golovnev

Sejauh yang saya tahu, tiga kelas sirkuit berlapis telah dipelajari. Dalam semua definisi ini, busur hanya diperbolehkan antara dua lapisan yang berdekatan.

Sirkuit disebut sinkron ( Harper 1977 ) jika semua gerbang disusun menjadi lapisan, dan input harus berada pada lapisan 0. (Definisi yang setara: untuk setiap gerbang $g$ , semua jalur dari input ke $g$ memiliki panjang yang sama.)
Sirkuit adalah sinkron secara lokal ( Belaga 1984 ) jika setiap input muncul tepat satu kali tetapi pada lapisan yang arbitrer.
Sebuah sirkuit berlapis ( Gal, Jang 2010 ) jika gerbang dan input disusun menjadi lapisan, input dapat terjadi beberapa kali pada lapisan yang berbeda. (Definisi yang setara: untuk setiap gerbang $g$ dan gerbang keluaran $o$ , semua jalur yang diarahkan dari $g$ ke $o$ memiliki panjang yang sama.)

Sangat mudah untuk melihat bahwa tiga kelas terdaftar dari yang paling lemah ke yang terkuat (dan kelas sirkuit tidak dibatasi bahkan lebih kuat).

Mengenai ukuran sirkit berlapis yang menghitung sirkit tak terbatas ukuran $s$ kita mengetahui hal berikut:

$s$ $s^2$
$\omega(s\log{s})$ $s$ $d$ $O(sd)$ $f$ $\omega(n\log{n})$ $f$ $O(\log{n})$ $O(n)$
Ada fungsi eksplisit

$\Omega(n\log{n})$ $O(n)$

$\Omega(n\log{n})$ $O(n)$

$n$

$f\colon\{0,1\}^n\to\{0,1\}^n$ $i$ $i$ $O(n)$ $\log{n}$ $n$ $n$ $f$ $\Omega(n\log{n})$ $n-1$ $\Omega(\log{n})$ $n$ $n$

Alex Golovnev
sumber

Bagaimana kecil dapat menjadi sirkuit boolean berlapis untuk fungsi dengan kompleksitas sirkuit

Jawaban: