Memutuskan apakah rangkaian

Apa kerumitan memutuskan apakah rangkaian dengan bit input dan bit output menghitung permutasi dari ? dengan kata lain, apakah setiap string bit di merupakan output dari rangkaian untuk beberapa input? Sepertinya masalah yang telah dipelajari, tetapi saya tidak dapat menemukan referensi.$\mathsf{NC}^0$n { 0 , 1 } n { 0 , 1 } $n$$n$$\{0,1\}^n$$\{0,1\}^n$

Kekerasan

Berikut komentar Anda pada pertanyaan, kami akan memanggil sirkuit di mana setiap bit output tergantung pada paling k bit masukan sebuah “NC ⁰ _k sirkuit.” Menggunakan istilah ini, masalah Anda adalah CoNp-lengkap dalam kasus NC ⁰ ₅ sirkuit. Yaitu, masalah berikut ini lengkap dengan CONP.

Instance : Sebuah sirkuit Boolean C dengan n bit input dan bit output n di mana setiap bit output paling banyak bergantung pada lima bit input.
Pertanyaan : Apakah pemetaan dari {0,1} ⁿ ke dirinya sendiri dihitung oleh C bijective?

Sebagai Kaveh berkomentar, itu jelas dalam coNP, bahkan tanpa terikat pada jumlah bit input di mana masing-masing bit output tergantung. Untuk membuktikan kekerasan CoNP, kami akan mengurangi 3SAT untuk melengkapi masalah saat ini. Gagasan kunci dari reduksi adalah sama dengan yang digunakan dalam makalah [Dur94] oleh Durand, yang saya sebutkan dalam komentar pada pertanyaan, tetapi keseluruhan reduksi jauh lebih sederhana dalam kasus kami.

Mengingat 3CNF rumus φ dengan n variabel dan m klausa, kami membangun sebuah sirkuit Boolean C dengan ( n + m ) masukan bit dan ( n + m ) bit output sebagai berikut. Kami memberi label bit input sebagai x ₁ , ..., x _n , y ₁ , ..., y _m , dan bit output sebagai x ′ ₁ , ..., x ′ _n , z ₁ , ..., z _m . Kami menganggap bahwa bit input x₁ ,…, x _n tentukan penugasan kebenaran ke n variabel dalam φ .

• x ′ _i = x _i untuk 1≤ i ≤ n . Artinya, n bit input pertama selalu disalin ke n bit output pertama.
• Untuk 1≤ i ≤ m , jika klausa i dari φ terpenuhi, maka z _i = y _i ⊕ y _{i +1} , di mana subscript ditafsirkan modulo m . Kalau tidak, z _i = y _i .

Perhatikan bahwa setiap bit output paling banyak bergantung pada lima bit input. Aku menghilangkan bukti kebenaran pengurangan, tetapi gagasan kunci (yang saya pinjam dari [Dur94]) adalah bahwa jika φ adalah satisfiable dan masukan bit x ₁ , ..., x _n ditetapkan untuk tugas memuaskan dari φ , maka yang m bit output z ₁ , ..., z _m dibatasi untuk memiliki bahkan paritas, dan karena itu rangkaian tidak bisa permutasi. Di sisi lain, jika bit input x ₁ , ..., x _n diatur ke penugasan satisf yang tidak memuaskan , maka bit output z₁ , ..., z _m dapat diatur untuk apa-apa; karena ini, jika φ tidak memuaskan, maka rangkaian adalah permutasi.

Ketertelusuran

Di sisi yang dapat ditelusuri, masalah Anda adalah dalam P jika sirkuit NC ⁰ ₂ . Ini ditunjukkan sebagai berikut. Secara umum, setiap bit keluaran dalam sirkuit Boolean untuk permutasi seimbang ; yaitu, tepat setengah dari string input mengatur bit output ke 1. Namun, setiap fungsi Boolean seimbang dari {0,1} ² hingga {0,1} adalah affine ; yaitu, salinan bit input tunggal, XOR dari dua bit input, atau negasi dari mereka. Oleh karena itu, pertama-tama kita dapat memeriksa bahwa setiap bit output seimbang, dan kemudian memeriksa bijektivitas dengan eliminasi Gaussian.

Saya tidak tahu kompleksitas dalam kasus sirkuit NC ⁰ ₃ atau dalam kasus sirkuit NC ⁰ ₄ .

Referensi

[Dur94] Bruno Durand. Pembalikan automata seluler 2D: beberapa hasil kompleksitas. Theoretical Computer Science , 134 (2): 387-401, November 1994. DOI: 10.1016 / 0304-3975 (94) 90244-5 .