Apakah penambahan dapat dilakukan dalam waktu kurang dari kedalaman 5?

Dengan menggunakan algoritma carry look ahead, kita dapat menghitung penambahan menggunakan kedalaman ukuran polinomial 5 (atau 4?) . Apakah mungkin mengurangi kedalaman? Bisakah kita menghitung penambahan dua bilangan biner menggunakan rangkaian keluarga ukuran polinomial dengan kedalaman kurang dari yang diperoleh dengan algoritma carry look forward? $AC^0$

Apakah ada lowerbin polinomial super untuk ukuran rangkaian rangkaian komputasi di mana adalah 2 atau 3? $AC^0_d$ $d$

Maksud saya kedalaman kedalaman alternatif.

cc.complexity-theory circuit-complexity lower-bounds upper-bounds Anonim
sumber

Bisakah Anda memberi tahu kami nama Anda? Siapa kamu? Selama sebulan terakhir ini orang-orang membuat nama pengguna baru di sini, mengajukan pertanyaan dan kemudian menghapus nama pengguna itu!

Tayfun Bayar

@ Geekster, umumnya orang tidak diharuskan membuat akun atau menggunakan nama asli mereka (namun disarankan untuk melakukannya karena berbagai alasan). Jika Anda memiliki keprihatinan umum tentang sesuatu, silakan gunakan Theoretical Computer Science Meta untuk meningkatkannya.

Kaveh

Ini bisa dipaksakan dengan memverifikasi bahwa tidak ada kedalaman-

4

$4$ AC

sirkuit dapat menghitung jumlah

-bit dari dua input

bit untuk beberapa

tetap ; hanya ada banyak fungsi boolean dari bit input yang dapat muncul di setiap kedalaman.

^{0}

$^{0}$

(m + 1)

$(m+1)$

m

$m$

m

$m$

mjqxxxx

@ mjqxxxx: Bagaimana Anda menegakkan batasan ukuran polinomial pada sirkuit AC0 ketika memaksa brute untuk m tetap? @ OP: Apakah kedalaman rangkaian terbaik 4 atau kedalaman 5 saat ini?

Robin Kothari

@ mjqxxxx: Setiap fungsi Boolean dapat dihitung dengan kedalaman

2

$2$ sirkuit. Sekarang, misalkan Anda menemukan untuk tetap Anda

m

$m$ sirkuit ukuran

s

$s$ . Bagaimana Anda menilai apakah ada sirkuit ukuran

c n

$cn$ untuk setiap

n

$n$ , di mana

c = s / m

$c=s/m$ , atau apakah hanya ada sirkuit berukuran

2^{ϵ n}

$2^{\epsilon n}$ , di mana

ϵ = (\log s) / m

$\epsilon=(\log s)/m$ ? Tidak ada cara untuk menyimpulkan informasi asimptotik dari contoh yang terbatas.

Emil Jeřábek mendukung Monica

Jawaban:

Menurut Teorema 3.1 dalam Alexis Maciel dan Denis Therien Threshen Circuits of Smallity-Depth memang ada rangkaian kedalaman-3 untuk menghitung penambahan dua angka.

The tepat terikat adalah dimana masalah yang memiliki kedalaman-2 sirkuit dengan kedua gerbang di bagian atas dan sirkuit yang sirkuit kedalaman satu (lihat makalah untuk penjelasan rinci tentang notasi). $\Delta_2 \cdot \mathsf{NC}^0_1$ $\Delta_2 = \Sigma_2 \cap \Pi_2$ $\mathsf{AC}^0$ $\vee,\wedge$ $\mathsf{NC}^0_1$ $\mathsf{NC}^0$

Ide bukti utama adalah:

Pertama, ungkapkan sirkuit Carry-lookahead sebagai $\mathsf{NC}^0\cdot\Delta_2\cdot\mathsf{NC}^0$
Selanjutnya, aktifkan properti penutupan untuk menulis ini sebagai $\Delta_2$ $\Delta_2\cdot\mathsf{NC}^0$
Akhirnya, gunakan fakta (juga terbukti di koran) bahwa $\mathsf{NC}^0 \subset \Delta_1\cdot\mathsf{NC}^0_1$

SamiD
sumber

Kedalaman 2 sirkuit memerlukan ukuran eksponensial untuk menghitung penambahan karena sirkuit kedalaman 2 harus berupa DNF atau CNF dan mudah untuk memverifikasi bahwa ada banyak minterm dan maxterms yang secara eksponensial.

Peringatan : bagian di bawah ini buggy . Lihat komentar di bawah jawabannya.

Cara saya menghitungnya, penambahan dapat dilakukan di kedalaman 3. Asumsikan dan adalah bit ke- dari dua angka, di mana adalah indeks LSB dan dari MSB. $a_i$ $b_i$ $i$ $0$ $n$

Mari kita menghitung th sedikit jumlahnya, dengan cara yang standar dengan membawa tampilan depan: $i$ $s_i$

s_{i} = a_{i} \oplus b_{i} \oplus c_{i}

$s_i = a_i \oplus b_i \oplus c_i$

di mana adalah XOR dan adalah carry yang dihitung sebagai: $\oplus$ $c_i$

c_{i} = \underset{j ∣ j < i}{⋁} (g_{j} \land p_{j})

$c_i = \bigvee_{j\mid j < i} (g_j \wedge p_j)$

dan berarti bahwa lokasi "menghasilkan" carry: $g_j$ $j$

g_{j} = (a_{j} \land b_{j})

$g_j = (a_j \wedge b_j)$

dan berarti bahwa carry diperbanyak dari ke : $p_j$ $j$ $i$

p_{j} = \underset{k ∣ j < k < i}{⋀} (a_{j} \lor b_{j})

$p_j = \bigwedge_{k\mid j < k < i} (a_j \vee b_j)$

Menghitung kedalaman, adalah kedalaman 2, dan adalah kedalaman 3. Sementara akan terlihat bahwa adalah kedalaman 4 atau 5, itu benar-benar juga hanya kedalaman 3 karena merupakan fanin perhitungan dibatasi kedalaman 3 sirkuit jadi salah satu dapat mendorong dua tingkat teratas ke bawah menggunakan rumus de-Morgan, sambil meniup ukuran rangkaian dengan jumlah polinomial. $p_j$ $c_i$ $s_i$

Noam
sumber

Saya tidak begitu mengerti bagaimana perhitungan fanin yang dibatasi dari sirkuit 3 secara otomatis adalah kedalaman 3. Jika, katakanlah, Anda menulis

, Anda dapat membuat yang pertama

sirkuit kedalaman 3 dengan

di atas, dan yang kedua

sirkuit kedalaman 3 dengan

s_{i}

$s_i$

(c_{i} \land \neg (a_{i} \oplus b_{i})) \lor (\neg c_{i} \land (a_{i} \oplus b_{i}))

$(c_i\land\neg(a_i\oplus b_i))\lor(\neg c_i\land(a_i\oplus b_i))$

⋁

$\bigvee$

⋀

$\bigwedge$ di atas. Saya tidak melihat bagaimana mendorong disjungsi atas ke bawah tanpa meningkatkan kedalaman satu per satu untuk menjelaskan ketidakcocokan antara jenis ikat di dua bagian. Ini dapat diperbaiki dengan mencatat bahwa

juga dapat dihitung dengan cara yang berbeda dengan sirkuit 3 kedalaman ...

c_{i}

$c_i$

Emil Jeřábek mendukung Monica

... dengan

di atas. Di sisi lain, semua sirkuit 3 kedalaman telah terikat kipas bawah, jadi saya akan menyebutnya kedalaman 2 1/2.

⋀

$\bigwedge$

Emil Jeřábek mendukung Monica

Itu sudah jelas. Apa yang saya tunjukkan adalah bahwa seperti yang tertulis, Anda tidak memiliki ATAU dua sirkuit

mendalam dengan DAN di atas. Anda memiliki ATAU dari dua sirkuit

kedalaman , salah satunya memiliki AND di atas, dan yang lainnya memiliki ATAU di atas. Saya ragu sirkuit seperti itu dapat dikonversi ke kedalaman

secara umum. Pikirkan tentang polinomial fan-in AND dan OR sebagai quantifiers. Anda dapat mengekspresikan

d

$d$

d

$d$

d

$d$

sebagai rumus prenex denganblok

quantifier, tetapi Anda membutuhkan

blok untuk mengekspresikan ...

(\forall x_{1} \exists x_{2} \dots Q x_{d} ϕ (x_{1}, \dots, x_{d})) \lor (\forall x_{1} \exists x_{2} \dots Q x_{d} ψ (x_{1}, \dots, x_{d}))

$(\forall x_1\exists x_2\dots Qx_d\phi(x_1,\dots,x_d))\lor(\forall x_1\exists x_2\dots Qx_d\psi(x_1,\dots,x_d))$

d

$d$

d + 1

$d+1$

Emil Jeřábek mendukung Monica

(\forall x_{1} \exists x_{2} \dots Q x_{d} ϕ (x_{1}, \dots, x_{d})) \lor (\exists x_{1} \forall x_{2} \dots \bar{Q} x_{d} ϕ (x_{1}, \dots, x_{d}))

$(\forall x_1\exists x_2\dots Qx_d\phi(x_1,\dots,x_d))\lor(\exists x_1\forall x_2\dots \overline Qx_d\phi(x_1,\dots,x_d))$

f_{n} (x_{1}, \dots, x_{n})

$f_n(x_1,\dots,x_n)$

A C_{d}^{0}

$AC^0_d$

d

$d$

x_{0} \oplus f_{n}

$x_0\oplus f_n$

A C_{d}^{0}

$AC^0_d$

C_{n} (x_{0}, \dots, x_{n})

$C_n(x_0,\dots,x_n)$

C_{n}

$C_n$

x_{0} = 1

$x_0=1$

A C_{d}^{0}

$AC^0_d$

\neg f_{n}

$\neg f_n$

A C_{d}^{0}

$AC^0_d$

f_{n}

$f_n$