Latar Belakang
Kompleksitas sirkuit didefinisikan sebagai himpunan rangkaian keluarga (yaitu rangkaian rangkaian, satu untuk setiap ukuran input) dengan kedalaman terikat dan ukuran polinomial yang dibangun menggunakan kipas-in tanpa batas AND, OR, dan NOT.
Fungsi paritas dengan input n- bit sama dengan XOR bit dalam input.
Salah satu lowerbound sirkuit pertama yang terbukti dalam kompleksitas sirkuit adalah sebagai berikut:
[FSS81], [Ajt83]: .
Pertanyaan:
Biarkan menjadi kelas fungsi yang dapat dihitung menggunakan sirkuit elektronik dengan kedalaman terbatas dan ukuran polinom menggunakan komponen elektronik seperti transistor. (Saya mengarang nama E C 0 , beri tahu saya jika Anda tahu nama yang lebih baik untuk ini).
Bisakah kita menghitung dalam praktiknya menggunakan sirkuit E C 0 ?
Bagaimana dengan fan-in tanpa batas DAN / ATAU? Bisakah kita menghitungnya dalam ?
catatan:
Posting ini berisi pertanyaan menarik tetapi OP tampaknya menolak untuk membuat posting lebih mudah dibaca dan memperbaiki kesalahpahaman di dalamnya karena beberapa alasan, jadi saya mem-posting ulang pertanyaan dari itu. (Akan lebih mudah untuk mengedit posting asli tetapi saat ini tidak ada perjanjian jika boleh mengedit posting pengguna lain dengan berat.)
Terkait:
Jawaban:
Saya bukan seorang insinyur listrik, tetapi mencari paten daring mengenai sirkuit pengalih untuk gerbang paritas, dan semua proposal (saya menemukan paten hanya sampai akhir tahun 1970-an) membahas masalah ukuran versus kedalaman. Ketiga paten saya telah melihat solusi mengusulkan kedalaman logaritmik, berdasarkan gerbang fanin-2. Jadi jawaban untuk pertanyaan pertama Anda mungkin "tidak".
JJ Moyer: Circuit Switching Cek Paritas, Paten Amerika Serikat US3011073, 1961
AF Bulver dkk.: Realisasi NAND Gate dari fungsi paritas n-input, Paten Amerika Serikat US3718904, 1973
PJ Baun, Jr .: Sirkuit Paritas, Paten Amerika Serikat US4251884, 1981
sumber
Johne, apa masalahmu? Anda mencoba berdebat tentang hal-hal yang tidak pernah diklaim oleh siapa pun. Tidak ada yang mengatakan bahwa paritas batas bawah menimbulkan beberapa batasan mendasar untuk menghitung XOR dengan sirkuit selain dari yang teorema tersebut berlaku (yaitu sirkuit AC ^ 0). Tidak ada asumsi tersembunyi atau implikasi terselubung di sini. Khususnya kita semua tahu misalnya bahwa adalah mungkin untuk menghitung XOR dengan sirkuit NAND berukuran polinomial dari kedalaman logaritmik, bahkan dengan fan-in yang konstan.
Kutipan Shannon sebagian besar juga tidak relevan. Tidak ada indikasi di sana bahwa ia bahkan menduga bahwa sirkuit AND-OR dengan kedalaman konstan perlu memiliki ukuran eksponensial untuk menghitung Paritas. Tentu saja dia bisa menebak, karena mudah untuk menduga ini harus benar setelah bermain dengan masalah untuk sementara waktu, tetapi jadi apa?
Anda benar-benar melewatkan intinya: membuktikan batas bawah sangat sulit, dan kita harus mulai di suatu tempat, dengan model paling sederhana. Ini pada dasarnya adalah rangkaian pertama batas bawah, tekniknya menghasilkan banyak ide menarik (termasuk bidang lain seperti teori pembelajaran), dan meskipun hasilnya masuk akal buktinya berwawasan luas dan sama sekali tidak sepele.
Fakta bahwa hasilnya tampak intuitif tidak membuatnya jelas; jika menurut Anda, berikan bukti bahwa paritas tidak dalam AC ^ 0. Semua orang tahu bahwa P tidak sama dengan NP juga dalam hal ini, tetapi tidak ada yang mendekati memiliki bukti.
Keluhan Anda di utas lain tentang gerbang NAND juga tidak masuk akal. Batas bawah ini berlaku sama baiknya untuk sirkuit dengan kedalaman konstan yang dibangun dari gerbang NAND, karena pada dasarnya sama. Memilih untuk menyatakan hasil dengan AND, ATAU, BUKAN hanyalah masalah kenyamanan. Jadi ini mungkin aplikasi dunia nyata dalam hal yang Anda suka: sirkuit kedalaman-konstan gerbang NAND menghitung paritas membutuhkan ukuran eksponensial. Itu memang memberikan batasan praktis, bahkan jika itu bukan hal yang paling penting. Dikatakan bahwa sirkuit XOR kecil untuk sejumlah besar n input harus memiliki kedalaman tumbuh dengan n atau gerbang selain NAND. Kenapa kamu tidak puas dengan ini?
Klaim Anda bahwa kedalaman rangkaian bukan merupakan masalah di dunia nyata juga sangat menyesatkan, karena kedalaman terkait langsung dengan waktu dan frekuensi maksimum di mana jam dapat beroperasi.
Ngomong-ngomong, komunitas CS sangat menyadari teori sirkuit boolean EE dan dibangun di atasnya, bertentangan dengan apa yang Anda klaim.
sumber
Tempat yang baik untuk menemukan gerbang XOR / XNOR kecepatan tinggi dan ringkas ada di sirkuit full-adders dan Hamming ECC (yang biasanya berada di jalur kritis).
Juga, masalah kedalaman rangkaian biasanya tidak menjadi perhatian dalam logika sinkron VLSI. Satu-satunya kedalaman konsekuensi adalah jalur kritis, yang menentukan periode jam maksimum. Sebagian besar logika kombinatorial menyebarkan hasil mereka di sebagian kecil dari waktu untuk jalur kritis. Jalur kritis cenderung terjadi dengan beberapa logika kombinatorial yang perlu melewati beberapa area yang tersebar di sebuah chip.
Ini dari Blog Kompleksitas Komputasi:
sumber