Apakah sirkuit AND & ATAU P-selesai?

Gerbang AND & OR adalah gerbang yang diberi dua input dan mengembalikan AND dan OR mereka. Apakah sirkuit dibuat hanya dari gerbang AND & OR, tanpa fanout, mampu melakukan perhitungan acak? Lebih tepatnya, apakah logspace komputasi waktu polinomial dapat direduksi menjadi sirkuit AND & OR?

Motivasi saya untuk masalah ini agak aneh. Seperti dijelaskan di sini , pertanyaan ini penting untuk perhitungan di dalam game komputer Dwarf Fortress .

Jika saya tidak salah mengerti apa yang Anda maksud dengan gerbang AND & OR, pada dasarnya gerbang komparator yang mengambil dua bit input dan y dan menghasilkan dua bit output x ∧ y dan x ∨ y . Dua bit output x ∧ y dan x ∨ y pada dasarnya adalah min ( x , y ) dan maks ( x , y ) .$x$$y$$x\wedge y$$x\vee y$$x\wedge y$$x\vee y$$(x,y)$$(x,y)$

Sirkuit komparator dibangun dengan menyusun gerbang komparator ini secara bersamaan tetapi memungkinkan tidak ada fan-out selain dari dua output yang dihasilkan oleh masing-masing gerbang . Jadi, kita bisa menggambar rangkaian pembanding menggunakan notasi di bawah ini (mirip dengan cara kita menggambar jaringan penyortiran).

Kita dapat mendefinisikan masalah nilai rangkaian pembanding (CCV) sebagai berikut: diberi rangkaian pembanding dengan input Boolean yang ditentukan, tentukan nilai output dari kawat yang ditunjuk. Dengan mengambil penutupan masalah CCV ini di bawah pengurangan ruang log, kita mendapatkan kelas kompleksitas CC , yang masalah lengkapnya mencakup masalah alami seperti pencocokan maksimal lex-first, pernikahan stabil, roomate stabil.

Dalam makalah baru-baru ini , Steve Cook, Yuval Filmus dan saya menunjukkan bahwa bahkan ketika kita menggunakan AC 0 banyak-satu penutupan, kita masih mendapatkan CC kelas yang sama. Sejauh pengetahuan kami pada saat ini, NL ⊆ CC ⊆ P. Dalam makalah kami, kami memberikan bukti bahwa CC dan NC tidak dapat dibandingkan (sehingga CC adalah subset P yang tepat), dengan memberikan pengaturan oracle di mana relativized CC dan relativized NC tidak ada bandingannya. Kami juga memberikan bukti bahwa CC dan SC tidak dapat dibandingkan.$^0$$\subseteq$$\subseteq$

(jawabannya tidak memenuhi syarat karena mengacu pada gerbang AND, ATAU yang terpisah tanpa batasan larangan keluar)

Artikel berikut tentang topik: Mayoritas Suara Pilih Automata, Ising Dynamics, dan P-Completeness

Kami menunjukkan bahwa dalam tiga atau lebih dimensi sistem ini dapat mensimulasikan rangkaian Boolean gerbang AND dan OR, dan karenanya P-complete . Artinya, memprediksi langkah-langkah waktu negara mereka di masa depan setidaknya sama sulitnya dengan masalah lain yang membutuhkan waktu polinomial pada komputer serial.

(...)

Masalah Nilai Sirkuit Monoton, di mana gerbang AND dan OR diizinkan tetapi BUKAN gerbang tidak, masih P-lengkap karena alasan berikut: menggunakan hukum De Morgan (...), kita dapat menggeser negasi kembali melalui gerbang sampai mereka hanya mempengaruhi input itu sendiri. Dengan demikian setiap masalah Nilai Sirkuit dapat dikonversi menjadi masalah Nilai Sirkuit Monoton dengan beberapa input dinegasikan. Konversi semacam ini, dari contoh masalah ke contoh masalah lain, disebut reduksi.