Minimum Pohon-lebar rangkaian untuk UTAMA

Berapakah lebar pohon minimum dari suatu sirkuit di atas $\{\wedge,\vee,\neg\}$ untuk menghitung MAJ?

Di sini MAJ $:\{0,1\}^n \rightarrow \{0,1\}$ menghasilkan 1 jika setidaknya setengah dari inputnya adalah $1$ .

Saya hanya peduli tentang ukuran sirkuit (seharusnya polinomial) dan bahwa input harus dibaca hanya sekali meskipun fan-out dari gerbang input dapat berubah-ubah (ini sangat mempengaruhi lebar pohon dari rangkaian - percabangan program yang diperoleh dari teorema Barrington dari MAJ $\in$ $\mathsf{NC}^1$ , ditafsirkan sebagai sirkuit miring, tidak membantu). Dan tentu saja lebar pohon adalah hal yang paling penting. Saya tidak peduli dengan kedalaman atau parameter lainnya.

Beberapa sirkuit umum untuk MAJ meliputi:

Sirkuit pohon Wallace (egTheorem 8.9 di sini ) yang menggunakan trik 3-ke-2 untuk menempatkan MAJ di $\mathsf{NC}^1$ ?
Sirkuit monoton Valiant $\mathsf{NC}^1$ untuk MAJ (mis. Teorema 4 di sini )
$\log^{O(1)}{n}$ menyortir jaringan mendalam sepertiBatchersemacam
Jaringan penyortiran AKS

Apakah ada di antara mereka yang terikat atau bahkan sebatas pohon polylogarithmic?

Atau sebenarnya,

Apakah ada alasan untuk percaya bahwa tidak ada sirkuit lebar pohon terbatas untuk MAJ?

Perhatikan bahwa setiap fungsi yang dihitung oleh sirkuit lebar pohon yang dibatasi dapat dihitung oleh sirkuit bahkan ketika tidak ada ketentuan baca-sekali melalui JansenSarma . Dengan demikian tidak masuk akal dari rangkaian keluarga seperti itu akan menunjukkan bahwa ikatan ini dapat diperketat lebih lanjut dalam kasus sirkuit baca-sekali. $\mathsf{NC}^1$

reference-request complexity-classes circuit-complexity treewidth SamiD
sumber

Mengapa hal ini tidak sepele untuk setiap

bahasa? Sejauh yang saya bisa lihat, rumus (yaitu, pohon) memiliki lebar pohon

, atau apakah saya kehilangan sesuatu?

{N C}^{1}

$\mathrm{NC}^1$

1

$1$

Emil Jeřábek

Saya pikir OP mengidentifikasi semua daun dari pohon rumus yang sesuai dengan variabel yang sama, yang menciptakan siklus.

Sasho Nikolov

Sirkuit untuk mayoritas dapat diimplementasikan dalam treewidth O (log n). Rangkaian hanya mensimulasikan algoritma online yang membaca bit input satu per satu dan menambahkan 1 ke nomor dengan O (log n) bit jika dan hanya jika inputnya 1. Perhatikan bahwa kedalaman rangkaian adalah O (n). Lihat Gambar 1 dari ( arxiv.org/pdf/1404.5565v1.pdf ). Sirkuit dengan kedalaman kecil belum tentu treewidth kecil karena seperti yang ditunjukkan Sasho Nikolov Anda perlu mengidentifikasi node yang sesuai dengan variabel input yang sama.

Mateus de Oliveira Oliveira

@MateusdeOliveiraOliveira Konstruksi yang Anda tunjukkan bagus dan sederhana dan hampir apa yang saya butuhkan. Yang benar-benar saya butuhkan adalah konstruksi yang bekerja di lebar pohon yang dibatasi (atau beberapa indikasi mengapa itu tidak mungkin). Saya akan menunggu beberapa hari untuk melihat apakah ada jawaban lain - jika tidak (jika Anda mengonversi komentar Anda menjadi jawaban) saya akan menyetujuinya.

SamiD

@SamiD Saya memperluas komentar ini menjadi sebuah jawaban. Saya belum memposting sebagai jawaban sebelumnya karena itu hanya setengah dari apa yang Anda minta.

Mateus de Oliveira Oliveira

Jawaban:

Menjawab setengah dari pertanyaan Samir.

Mari menjadi DAG dan menjadi dua himpunan bagian dari simpul dari . Kami menyatakan dengan himpunan semua tepi dalam dengan satu titik akhir di dan titik akhir lainnya di . Jika $G=(V,E)$ $V_1,V_2\subseteq V$ $G$ $E(V_1,V_2)$ $G$ $V_1$ $V_2$ $\omega = (v_1,...,v_n)$ $G$

o w (G, ω) = max_{i} | E ({v_{1}, . . ., v_{i}}, {v_{i + 1}, . . ., v_{n}} |

$\mathbf{ow}(G,\omega) = \max_{i}\; |E(\{v_1,...,v_i\},\{v_{i+1},...,v_n\}|$

ω

$\omega$

G

$G$

o w (G) = min_{ω} o w (G, ω),

$\mathbf{ow}(G) = \min_{\omega}\; \mathbf{ow}(G,\omega),$

G

$G$

G

$G$

c w (G)

$\mathbf{cw}(G)$

G

$G$ , terlepas dari apakah pemesanan topologi atau bukan. Kami memiliki urutan ketidaksetaraan berikut: mana dan adalah masing-masing pathwidth dan treewidth dari .

t w (G) \leq p w (G) \leq c w (G) \leq o w (G),

$\mathbf{tw}(G) \leq \mathbf{pw}(G) \leq \mathbf{cw}(G)\leq \mathbf{ow}(G),$

p w (G)

$\mathbf{pw}(G)$

t w (G)

$\mathbf{tw}(G)$

G

$G$

Kami mengklaim bahwa UTAMA bit dapat dihitung dalam lebar-online , dan karenanya dalam treewidth . Rangkaian mensimulasikan algoritma online yang membaca satu bit input pada suatu waktu dan menambahkan ke counter dengan bit jika dan hanya jika . Pada awal, penghitung diinisialisasi ke $n$ $O(\log n)$ $O(\log n)$ $b$ $b$ $O(\log n)$ $b=1$ $0$ . Pada akhirnya rangkaian menerima jika dan hanya jika nilai penghitung lebih besar dari n / 2. Sangat mudah untuk melihat bahwa gerbang sirkuit ADD yang menambahkan satu ke register register dapat dipesan secara topologi sedemikian rupa sehingga memiliki lebar online konstan, karena sirkuit ini hanya perlu menerapkan operasi carry on. Total sirkuit adalah urutan sirkuit mana output dicolokkan ke input , dan output dicolokkan ke masukan dari COMP. Sekarang jika kita secara topologi memesan total sirkuit sedemikian rupa sehingga semua gerbang muncul sebelum gerbang dan semua gerbang $C=(ADD_1,ADD_2,...,ADD_n,COMP)$ $ADD_i$ $ADD_{i+1}$ $ADD_n$ $C$ $ADD_i$ $ADD_{i+1}$ $ADD_n$ muncul di depan gerbang COMP, maka urutan topologi ini memiliki lebar online . Konstruksi ini diilustrasikan pada Gambar 1 dari makalah saya untuk menunjukkan bahwa amplifikasi probabilitas dapat dilakukan dalam lebar online logaritmik. $O(\log n)$

Obs: Kedalaman sirkuit C adalah . $O(n)$

Mateus de Oliveira Oliveira
sumber

Sebagai komentar sampingan, melakukan sirkuit yang sama tetapi sebagai pohon biner (dengan output di root) daripada path memberikan sirkuit dengan treewidth O (log n) dan kedalaman O (log n)

daniello

Tampaknya terjemahan langsung ke pohon akan memberikan kedalaman O ((log n) ^ 2) karena kita akan membutuhkan kedalaman O (log n) untuk setiap adder. Tetapi benar bahwa treewidth akan menjadi O (log n).

Mateus de Oliveira Oliveira

Tentu saja Anda benar, terima kasih! Tampaknya jika penambahan diimplementasikan sebagai DNF maka kita mendapatkan treewidth dan kedalaman O (log n), tetapi ukuran .

O (n^{3})

$O(n^3)$

daniello

Masalahnya dengan mewakili penambah sebagai DNF adalah bahwa hal itu berpotensi dapat meningkatkan treewidth, karena sekarang setiap variabel akan dibagikan (sekilas secara polinomi) banyak klausa. Saran Anda untuk mengurangi kedalaman menjadi O (log n) akan bekerja jika Anda dapat menunjukkan bahwa penambahan dua angka dengan bit O (log n) dapat dilakukan dalam kedalaman konstan dan treewidth logaritmik.

Mateus de Oliveira Oliveira

Nah - untuk setiap fungsi Boolean pada masukan bit dan keluaran bit DNF memiliki kedalaman , ukuran , dan treewidth sejak menghapus daun masukan + keluaran gerbang set independen ...

a

$a$

b

$b$

2

$2$

2^{a} + a + b

$2^a + a + b$

\leq a + b

$\leq a+b$

daniello

Menjawab bagian lain dari pertanyaan - ini adalah sketsa bukti untuk batas bawah untuk treewidth untuk beberapa konstanta . Batasnya tidak tergantung pada ukuran atau aspek lain dari rangkaian. Di sisa argumen adalah sirkuit, adalah treewidth dari dan adalah jumlah gerbang input. $c \cdot \log n$ $c$ $C$ $t$ $C$ $n$

Langkah pertama adalah menggunakan lemma pemisah seimbang untuk grafik treewidth terikat . Gerbang (termasuk gerbang input) sirkuit dapat dipartisi menjadi tiga bagian , dan , sehingga dan keduanya dan mengandung setidaknyagerbang masukan, dan tidak ada busur (kabel) antara dan . $L$ $R$ $S$ $|S| \leq t+1$ $L$ $R$ $n/3-|S|$ $L$ $R$

Di sisa buktinya, satu-satunya properti rangkaian yang akan kita gunakan adalah partisi ini - jadi buktinya benar-benar memberikan batas bawah pada ukuran pemisah seimbang seperti di atas. $S$

Setelah di tangan kami membangun sirkuit dari sebagai berikut: untuk setiap gerbang di membuat dua gerbang lagi dan , dan membuat dan diumpankan ke . Untuk semua kabel yang mengarah ke dari buat mereka masuk ke sebagai gantinya. Untuk semua kabel yang mengarah ke dari membuatnya menjadi . Biarkan $(L,S,R)$ $C'$ $C$ $g$ $S$ $g_L$ $g_R$ $g_L$ $g_R$ $g$ $g$ $L$ $g_L$ $g$ $R$ $g_R$

S^{'} = {g, g_{L}, g_{R} : g \in S} .

$S' = \{g, g_L, g_R : g \in S\}.$

Untuk masing-masing assingments ke membuat sirkuit yang menghasilkan 1 jika (a) penugasan ke gerbang input membuat output benar dan (b) penugasan ke gerbang input menetapkan semua gerbang seperti yang diduga. Sebut sirkuit ini , , untuk . Perhatikan bahwa sirkuit secara alami dipecah menjadi dua dan sedemikian rupa sehingga hanya tergantung pada gerbang input , hanya tergantung pada gerbang input dari $2^{|S'|}$ $S'$ $C'$ $S'$ $C_1$ $C_2$ $C_3 \ldots C_x$ $x \leq 8^t$ $C_i$ $C_i^L$ $C_i^R$ $C_i^L$ $L \cup S'$ $C_i^R$ $R \cup S'$ , dan untuk setiap tugas ke gerbang masukan yang kita miliki bahwa . $C_i = C_i^L \wedge C_i^R$

Karena setiap penugasan ke gerbang input konsisten dengan beberapa tebakan untuk apa yang terjadi di kami memiliki . Jadi kita telah menulis ulang sirkuit sebagai OR (dari fanin ) dari AND (dari fanin ) di mana nomor gerbang AND diumpankan dengan output masing-masing dari dan $S'$ $C' = C_1 \vee C_2 \vee C_3 \ldots \vee C_x$ $C$ $8^t$ $2$ $i$ $C_i^L$ $C_i^R$

Biarkan menjadi himpunan gerbang AND paling atas. Pertama-tama kita akan membuktikan bahwa. Ini memberi ikatan lebih rendah pada . Kami kemudian akan membuktikan ikatan yang lebih baik. $Z$ $2^{|Z|} \geq n/3-|S|$ $\log \log n$ $t$

Misalkan, Dan menganggap wlog yang berisi masukan gerbang kurang dari . Kemudian kedua dan mengandung setidaknyagerbang input. Dengan prinsip lubang merpati ada dua angka yang berbeda dan sedemikian rupa sehingga ada dua tugas yang berbeda untuk gerbang input , satu yang menetapkan gerbang menjadi true, satu yang menetapkan , sedemikian rupa sehingga sirkuit , semua menampilkan hal yang sama. Tapi ada tugas untuk gerbang input di $2^{|Z|} < n/3-|S|$ $L$ $R$ $L$ $R$ $n/3-|S|$ $i$ $j$ $L$ $i$ $j$ $C_1^L$ $C_2^L \ldots C_x^L$ $R$ sehingga MAJORITY menghasilkan FALSE jika gates di disetel ke true, dan MAJORITY menghasilkan TRUE jika gerbang di disetel ke true. Ini adalah kontradiksi, dan menyiratkan bahwa treewidth setidaknya . $i$ $L$ $j$ $L$ $2^{|Z|} \geq n/3-|S|$ $\log \log n$

Kami sekarang menunjukkan batas yang lebih baik:. Asumsikan wlog yang berisi masukan gerbang kurang dari . Kemudian kedua L dan R mengandung setidaknyagerbang input. Pertimbangkan "semua palsu" tugas untuk . Misalkan adalah jumlah gerbang input terkecil yang harus disetel ke true sedemikian sehingga MAJ menghasilkan BENAR, mengingat bahwa semua disetel ke false. $|Z| \geq n/3-|S|$ $L$ $R$ $n/3-|S|$ $L$ $r$ $R$ $L$

Sejak pengaturan untuk semua palsu dan persis gerbang input untuk output merek benar MAYORITAS harus ada beberapa sehingga output TRUE, wlog ini . Semua penugasan ke dengan gerbang input kurang dari benar harus menetapkan menjadi false. Karena pengaturan gerbang input ke true dan gerbang input dari ke true membuat output UTAMA , pengaturan gerbang ke true harus membuat setidaknya satu $L$ $r$ $R$ $1$ $i$ $C_i^L$ $C_1^L$ $R$ $r$ $C_1^R$ $1$ $L$ $r-1$ $R$ $1$ $1$ $L$ $C_i^L$ outpur true untuk . wlog kita dapat mengasumsikan . Kemudian semua penugasan ke yang mengatur paling banyak gerbang input menjadi true harus menetapkan ke false, dan seterusnya - kita dapat mengulangi argumen ini kali. Tetapi ini berarti bahwa, memberikan batas bawah untuk . $i \neq 1$ $i=2$ $R$ $r-2$ $C_2^R$ $r$ $|Z| \geq r \geq n/3-|S|$ $c \cdot \log n$ $t$

[Aku tahu sketsa ini sedikit bergelombang di beberapa tempat, bertanya apakah ada sesuatu yang tidak jelas ...]

daniello
sumber