Konsekuensi praktis dari

10

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.AC0

Fungsi paritas dengan input n- bit sama dengan XOR bit dalam input.n

Salah satu lowerbound sirkuit pertama yang terbukti dalam kompleksitas sirkuit adalah sebagai berikut:

[FSS81], [Ajt83]: .AC0


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).EC0EC0

  1. Bisakah kita menghitung dalam praktiknya menggunakan sirkuit E C 0 ?EC0

  2. Bagaimana dengan fan-in tanpa batas DAN / ATAU? Bisakah kita menghitungnya dalam ?EC0

  3. AC0AC0

  4. AC0


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:

Kaveh
sumber
NC0AC0
AC0
AC0
@ Harun: Saya juga tidak ingat banyak tapi saya pikir loop terutama untuk elemen memori seperti flipflops dan sistem sekuensial. Saya tidak berpikir sulit untuk menghubungkan kompleksitas rangkaian dengan sirkuit logis / digital khususnya sistem kombinatorial, pertanyaannya adalah bagaimana menghubungkan konsep seperti kedalaman dan kipas ke sirkuit elektronik yang terbuat dari transistor. Mungkin saya harus menanyakannya di Physics.SE.
Kaveh
3
@ Tsuyoshi Ito: Terima kasih. Saya baru saja memeriksanya di Wikipedia, tampaknya seseorang dapat dengan mudah mengimplementasikan gerbang AND dan OR tanpa batas menggunakan nomor linear NMOS . Struktur sirkuit sederhana dan tidak berubah dengan jumlah input ke gerbang. Di sisi lain, sirkuit XOR yang terbuat dari transistor NMOS tampaknya lebih rumit, saya tidak tahu apakah timbangannya baik dengan peningkatan fan-in.
Kaveh

Jawaban:

10

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

Hermann Gruber
sumber
Sangat menarik.
Antonio E. Porreca
6

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.

David
sumber
2
terima kasih atas jawabannya, tetapi sebagian besar dari jawaban Anda adalah komentar yang diarahkan ke johne dan bukan untuk pertanyaan saya. Saya mengerti bahwa Anda mungkin telah memposting ini sebagai jawaban karena Anda tidak dapat berkomentar tetapi saya tidak ingin pertanyaan ini berubah menjadi diskusi antara kalian berdua, jadi bisakah Anda memindahkan bagian dari jawaban Anda yang diarahkan kepadanya ke pertanyaan terkait diposting olehnya? (atau ke diskusi meta ) Terima kasih sebelumnya.
Kaveh
1

1.6223.822

s=abcin

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.

nO(1)

AT2=Ω(n2)

Ini dari Blog Kompleksitas Komputasi:

Hal ini menimbulkan pertanyaan: apakah beberapa orang di dunia nyata benar-benar ingin membangun kedalaman konstan polsize fanin tak terbatas DAN-ATAU-TIDAK untuk PARITY, dan apakah hasil ini memberi tahu mereka mengapa mereka tidak bisa?

2n/n

λ(3)=8

XYZ=X(YZ+YZ)+X(YZ+YZ)

μ(3)

X1X2Xn

4(n1)

John
sumber
Tahnks johne untuk jawabannya, tetapi saat ini saya sedikit kekurangan waktu tetapi saya akan membaca jawaban Anda lebih hati-hati dan melihat artikel yang telah Anda tautkan ketika saya menemukan waktu luang. Saya telah berbicara dengan beberapa teman dari departemen EE juga dan telah belajar beberapa hal menarik yang akan saya posting.
Kaveh