Sirkuit Boolean terkecil untuk menghasilkan bahasa

Pertimbangkan bahasa tidak kosong panjang string biner . Saya dapat menggambarkan dengan rangkaian Boolean dengan input dan satu output sedemikian rupa sehingga benar iff : ini sudah terkenal.n L C n C ( w ) w ∈ $L$$n$$L$$C$$n$$C(w)$$w \in L$

Namun, saya ingin mewakili dengan Boolean sirkuit dengan output dan sejumlah masukan, mengatakan , sehingga himpunan nilai-nilai output untuk masing-masing kemungkinan input adalah persis .C ′ n m C ′ 2 m$L$$C'$$n$ $m$$C'$$2^m$$L$

Mengingat , bagaimana saya bisa menemukan sirkuit dengan ukuran minimal, dan apa kerumitannya? Apakah ada hubungan antara batas yang diketahui tentang ukuran sirkuit jenis pertama ( ) dan sirkuit jenis kedua ( ) ini, atau kompleksitas menemukannya?C ′ C C $L$$C'$$C$$C'$

(Perhatikan bahwa ada semacam dualitas dalam pengertian berikut: mengingat , saya dapat dengan mudah memutuskan apakah kata input ada dalam dengan mengevaluasi rangkaian, tetapi pada umumnya NP-hard untuk menemukan beberapa kata dalam dengan menemukan sebuah tugas sedemikian rupa sehingga hasilnya benar. Mengingat itu juga NP-sulit untuk memutuskan apakah beberapa kata input dalam karena saya harus melihat apakah tugas menghasilkan sebagai output, tetapi mudah untuk menemukan beberapa kata dalam dengan mengevaluasi sirkuit pada input sembarang.)w L L C ′ w L w $C$$w$$L$$L$$C'$$w$$L$$w$$L$

Saya akan menunjukkan koneksi sederhana ke sirkuit nondeterministic, dan berkomentar singkat tentang kekerasan kriptografi.

Untuk , tentukan kerumitan gambar, yang dilambangkan , sebagai jumlah gerbang minimal dalam setiap (fanin-two, AND / OR / NOT) sirkuit Boolean yang gambarnya . Pertanyaannya bertanya tentang kompleksitas komputasi , diberikan representasi tabel kebenaran (string dengan panjang ). i m c ( S ) C : { 0 , 1 } m → { 0 , 1 } n S i m c ( S ) S 2 $S \subseteq \{0, 1\}^n$$imc(S)$$C: \{0, 1\}^m \rightarrow \{0, 1\}^n$$S$$imc(S)$$S$$2^n$

Juga menentukan kompleksitas rangkaian nondeterministic dari , yang kita menotasikan , sebagai terkecil nondeterministic sirkuit menerima persis . Yaitu, kita membutuhkan yang iff . Ini adalah gagasan standar, yang digunakan untuk mendefinisikan kelas non-seragam : ini adalah kelas semua set , dengan , sedemikian rupa sehingga .n c c ( S ) C ( x , y ) : { 0 , 1 } n + m ′ → { 0 , 1 } S C x ∈ S ∃ y : C ( x , y ) = 1 N P / p o l y S = { S n } n > $S$$ncc(S)$$C(x, y): \{0, 1\}^{n + m'} \rightarrow \{0, 1\}$$S$$C$$x \in S$$\exists y: C(x, y) = 1$$NP/poly$$S = \{S_n\}_{n > 0}$ n c c ( S n ) ≤ p o l y ( n $S_n \subseteq \{0, 1\}^n$$ncc(S_n) \leq poly(n)$

Yang ingin saya tunjukkan adalah bahwa . Kedua arah ketidaksetaraan ini mudah diverifikasi. $imc(S) = ncc(S) \pm O(n)$

Biarkan menunjukkan kompleksitas sirkuit deterministik. Menggunakan Razborov-Rudich, makalah yang disebutkan oleh Dai Le menunjukkan (secara kasar berbicara di sini) bahwa berdasarkan asumsi kriptografi tertentu, secara komputasi sulit untuk membedakan tabel kebenaran dengan kecil, dari tabel kebenaran benar-benar acak ( dengan hampir-maksimal). Random juga memiliki hampir-maksimal, dan kami tentu saja memiliki . Jadi masalah Anda sulit di bawah asumsi yang sama.S d c c ( S ) S d c c ( S ) S n c c ( S ) n c c ( f ) ≤ d c c ( f $dcc(S)$$S$$dcc(S)$$S$$dcc(S)$$S$$ncc(S)$$ncc(f) \leq dcc(f)$

Manakah yang lebih sulit untuk dihitung dengan diberikan tabel kebenaran untuk , atau ? Apakah ada pengurangan? Saya tidak tahud c c ( S ) n c c ( S $S$$dcc(S)$$ncc(S)$

Anda harus melihat makalah ini oleh Kabanets dan Cai. Saya akan mengutip abstrak dari makalah ini:

Kami mempelajari kompleksitas masalah minimisasi rangkaian: dengan tabel kebenaran fungsi Boolean dan parameter s , tentukan apakah f dapat diwujudkan dengan ukuran sirkuit Boolean paling banyak di s . Kami berpendapat mengapa masalah ini tidak mungkin di P (atau bahkan di P / p o l y ) dengan memberikan sejumlah konsekuensi mengejutkan dari asumsi semacam itu. Kami juga berpendapat bahwa membuktikan masalah ini menjadi N P -Lengkap (jika memang benar) akan berarti membuktikan sirkuit yang kuat batas bawah untuk kelas E , yang muncul di luar teknik yang dikenal saat ini.$f$$s$$f$$s$$\mathsf{P}$$\mathsf{P}/\mathsf{poly}$$\mathsf{NP}$$\mathsf{E}$

$C'$$F:\{0,1\}^m \rightarrow L$$C'_1,C'_2,\ldots,C'_n$$C'_i$$i^{\rm th}$$F$$C'_i$$\{0,1\}^m\rightarrow \{0,1\}$$C'_i$