Memutuskan apakah suatu NC

Saya ingin bertanya tentang kasus khusus dari pertanyaan " Memutuskan apakah sirkuit NC ^{0 yang} diberikan menghitung permutasi " oleh QiCheng yang telah dibiarkan tidak terjawab.

Sirkuit Boolean disebut sirkuit NC ⁰ _k jika setiap gerbang keluaran secara sintaksis bergantung pada paling banyak gerbang input k . (Kami mengatakan bahwa gerbang keluaran g secara sintaksis tergantung pada gerbang input g ′ ketika ada jalur terarah dari g ′ ke g dalam rangkaian yang dipandang sebagai grafik asiklik terarah.)

Dalam pertanyaan tersebut di atas, QiCheng bertanya tentang kompleksitas masalah berikut, di mana k adalah konstanta:

Misalnya : Sebuah NC ⁰ _k sirkuit dengan n masukan-bit dan n keluaran-bit.
Pertanyaan : Apakah sirkuit yang diberikan menghitung permutasi pada {0, 1} ⁿ ? Dengan kata lain, apakah fungsi yang dikomputasi oleh rangkaian merupakan hasil dari {0, 1} ⁿ hingga {0, 1} ⁿ ?

Ketika Kaveh mengomentari pertanyaan itu, mudah untuk melihat bahwa masalahnya ada di dalam CoNP. Dalam sebuah jawaban, saya menunjukkan bahwa masalahnya adalah melengkapi-TNP untuk k = 5 dan bahwa itu dalam P untuk k = 2.

Pertanyaan . Apa kompleksitas untuk k = 3?

Klarifikasi pada 29 Mei 2013 : “Permutasi pada {0, 1} ⁿ ” berarti pemetaan dua arah dari {0, 1} ⁿ ke dirinya sendiri. Dengan kata lain, masalahnya bertanya apakah setiap string n- bit adalah output dari rangkaian yang diberikan untuk beberapa string input n- bit.

Masalah dengan ini adalah coNP-hard (dan karenanya coNP-complete).$k=3$

Untuk membuktikan ini, saya akan mengurangi dari 3-SAT untuk komplemen dari masalah ini (untuk diberikan sirkuit, apakah sirkuit memberlakukan fungsi non-bijective).$NC_3^0$

Pertama definisi awal yang akan membantu:

Kami mendefinisikan grafik berlabel sebagai grafik terarah, beberapa di antaranya memiliki label literal, dengan properti yang setiap verteks memiliki satu tepi masuk yang tidak berlabel, satu tepi masuk berlabel, atau dua tepi masuk yang tidak berlabel.

Pengurangan

Misalkan kita memiliki rumus 3-SAT terdiri dari m klausa, masing-masing berisi tiga literal. Langkah pertama adalah membuat grafik berlabel G dari ϕ . Grafik berlabel ini berisi satu salinan gadget berikut (maaf untuk diagram yang mengerikan) untuk setiap klausa dalam ϕ . Tiga sisi berlabel L1, L2, dan L3 sebaliknya diberi label dengan literal dalam klausa.$\phi$$m$$G$$\phi$$\phi$

   |
   |               |
   |               |
   |               O<-----\
   |               ^      |
   |               |      |
   |               |      |
   |        /----->O      |
   |        |      ^      |
   |        |      |      |
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |L1    |L2    |L3
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |      |      |
   |        \------O------/
   |               ^
   |               |
   |               |
   |               O
   |               ^
   |               |
   |

Gadget (satu untuk setiap klausa) semuanya diatur dalam satu siklus besar dengan bagian bawah satu gadget yang terhubung ke bagian atas yang berikutnya.

Perhatikan bahwa pengaturan gadget ini sebenarnya membentuk grafik berlabel (setiap titik memiliki indegree 1 atau 2 dengan hanya tepi yang mengarah ke simpul indegree 1 yang dilabeli).

$\phi$$G$$\phi$$NC_3^0$$n+v$$n$$\phi$$v$$G$$\phi$$G$$x$$\phi$$x$$x_{in}$$x_{out}$$l$$l = x$$l_{in} = x_{in}$$l$$l = \neg x$$l_{in} = \neg x_{in}$$v$$G$$v$$v_{in}$$v_{out}$

Ada empat jenis bit keluaran:

$x$$\phi$$x_{out} = x_{in}$

$v$$(u, v)$$v_{out} = v_{in} \oplus u_{in}$

$v$$(u, v)$$l$$v_{out} = v_{in} \oplus (u_{in} \land l_{in})$$l_{in}$$x_{in}$$x$$l$

$v$$(u, v)$$(w, v)$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$

$NC_3^0$

$\phi$

$\phi$

$\phi$$G$

$\phi$$G$

$NC_3^0$

Pertimbangkan empat jenis bit keluaran:

$x$$\phi$$x_{out} = x_{in}$$x_{in}$

$v$$(u, v)$$v_{out} = v_{in} \oplus u_{in}$$G$$v_{out} = v_{in} \oplus u_{in} = 0 \oplus 0 = 0$$v_{out} = v_{in} \oplus u_{in} = 1 \oplus 1 = 0$

$v$$(u, v)$$l$$v_{out} = v_{in} \oplus (u_{in} \land l)$$l$$v_{in}$$v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 0) = v_{in} = 0$$l$$v_{in}$$(u, v)$$u$$u_{in} = 1$$u_{in} = v_{in}$$l$$v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 1) = v_{in} \oplus u_{in} = v_{in} \oplus v_{in} = 0$

$v$$(u, v)$$(w, v)$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$

$v$$u$$w$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$$u_{in}$$u_{in} = L1$$w_{in}$$w_{in} = L2$$v_{in}$$v_{in} = L1 \lor L2$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = (L1 \lor L2) \oplus (L1 \lor L2) = 0$

$v$$u$$w$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$$u_{in}$$u_{in} = L1 \lor L2$$w_{in}$$w_{in} = L3$$v_{in} = 1$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 1 \oplus ((L1 \lor L2) \lor L3) = 1 \oplus (L1 \lor L2 \lor L3) = 1 \oplus 1 = 0$$(L1 \lor L2 \lor L3) = 1$

$NC_3^0$

$\phi$

$\phi$$NC_3^0$

$x_{in}$$x$$\phi$$x$

$S$$v$$G$$v_{in}$

Kami akan membuktikan lemmas berikut di bawah ini:

$S$$S$

$S$$S$

$S$$G$$S$$S$

$(L1 \lor L2 \lor L3)$$(u, v)$$L$$v_{out} = v_{in} \oplus (u_{in} \land L)$$L = 0$$v_{out} = v_{in} \oplus (u_{in} \land L) = v_{in} \oplus (u_{in} \land 0) = v_{in} \oplus 0 = v_{in}$$v_{in}$$v$$S$$S$

$S$$NC_3^0$

Yang tersisa hanyalah membuktikan lemma.

$G$$S$$S$$v_{out} = v_{in} \oplus X$$X$$v$$S$$X$$v_{in} = v_{out} \oplus X$$v$$S$

$S$$S$

Bukan jawaban yang dicari penulis, lihat komentar yang menjelaskan "permutasi" dalam konteks ini.

Saya mengubah ukuran set dominasi minimum untuk diagram inklusi grup permutasi monogenik: https://oeis.org/A186202

Yang harus Anda lakukan adalah menguji satu anggota dari setiap dekomposisi siklus utama.

Untuk setiap siklus prima seharusnya cukup untuk mengkodekan elemen sebagai (10101010 ...), lalu (01010101 ..)?

------ Klarifikasi ------ Tujuan dari pendekatan ini adalah untuk memodelkan 2 uji kasus Anda sebagai digraf. Jika satu test case yang sukses menyiratkan case test yang berhasil lainnya, maka Anda hanya perlu menguji set dominasi min digaph ruang tes ini. Dalam ruang permutasi OEIS A186202 adalah maks yang harus Anda uji untuk mendeteksi subkelompok non-sepele atau membuktikan tidak ada; jumlah ini masih besar tetapi jauh lebih kecil dari n !.

--Musing-- Dengan menggunakan n-1 nol dan 1 satu dalam iterasi Anda dapat mendeteksi permutasi tetap yang Anda cari. Setelah itu di O (n {(n-1) \ pilih (k-1)} (2 ^ (k-1)) Anda dapat menguji bahwa setiap set variabel (k-1) tidak mempengaruhi setiap indeks dari shuffle Karena k adalah polinomial, apakah saya melewatkan sesuatu?