Sirkuit Boolean dan Kompleksitas Sirkuit

Sirkuit Boolean menghitung fungsi melalui jaringan gerbang logika, dan kompleksitas sirkuit mengukur masalah berdasarkan ukuran dan kedalaman sirkuit yang dibutuhkan untuk menyelesaikannya, menawarkan pandangan komputasi yang paralel dan berorientasi perangkat keras.

Definition

Sirkuit Boolean adalah graf berarah asiklik dari gerbang logika yang menghitung fungsi dari masukan biner dengan panjang tetap; kompleksitas sirkuit mempelajari jumlah gerbang minimal, kedalaman, atau sumber daya struktural lainnya yang diperlukan untuk menghitung keluarga fungsi Boolean tertentu.

Scope

Topik ini mencakup sirkuit dan formula Boolean, ukuran dan kedalaman sebagai tolok ukur kompleksitas, model seragam versus non-seragam, kelas kedalaman rendah seperti NC dan AC, hubungan antara batas bawah sirkuit dan pemisahan kelas kompleksitas, serta hasil batas bawah yang penting untuk keluarga sirkuit terbatas.

Core questions

• Bagaimana pandangan komputasi berbasis jaringan gerbang berbeda dari mesin sekuensial?
• Apa yang diukur oleh ukuran dan kedalaman sirkuit, dan bagaimana kaitannya dengan waktu dan paralelisme?
• Mengapa batas bawah sirkuit menjadi jalur menuju pemisahan kelas kompleksitas?
• Batas bawah apa saja yang diketahui, dan hambatan apa yang menghalangi batas yang lebih kuat?

Key theories

Non-uniformitas dan kelas P/poly

Sirkuit memungkinkan mesin yang berbeda untuk setiap panjang masukan, menghasilkan kelas non-seragam P/poly yang mengandung P; menunjukkan masalah NP-lengkap tidak memiliki sirkuit berukuran polinomial akan memisahkan P dari NP, memotivasi batas bawah sirkuit.

Batas bawah untuk sirkuit terbatas

Batas bawah yang kuat diketahui untuk keluarga terbatas, seperti ukuran eksponensial yang diperlukan untuk sirkuit kedalaman konstan yang menghitung paritas, meskipun batas bawah untuk sirkuit umum tetap sulit dicapai.

Clinical relevance

Sirkuit adalah model alami dari perangkat keras digital, sehingga kompleksitas sirkuit memberikan informasi tentang desain chip dan batasan komputasi paralel; kelas kedalaman rendah menangkap apa yang dapat dihitung dengan cepat menggunakan banyak prosesor, dan batas bawah sirkuit adalah strategi utama dalam upaya jangka panjang untuk menyelesaikan pertanyaan seperti P versus NP.

History

Shannon menghubungkan aljabar Boolean dengan sirkuit sakelar pada tahun 1937, dan kompleksitas sirkuit berkembang sebagai disiplin ilmu pada tahun 1980-an ketika Furst, Saxe, Sipser, dan lainnya membuktikan batas bawah kedalaman konstan untuk paritas, dan Razborov serta Smolensky mengembangkan metode aljabar, sebelum hambatan bukti alami mengungkapkan mengapa batas bawah umum begitu sulit dicapai.

Key figures

• Claude Shannon
• Alexander Razborov
• Andrew Yao
• Roman Smolensky

Seminal works

• aroraBarak2009
• vollmer1999

Frequently asked questions

Bagaimana sirkuit berbeda dari mesin Turing?

Mesin Turing adalah satu perangkat yang menangani masukan dari semua ukuran langkah demi langkah, sedangkan sirkuit adalah jaringan gerbang tetap untuk satu panjang masukan, dengan sirkuit terpisah untuk setiap panjang. Non-uniformitas ini menjadikan sirkuit model alami perangkat keras dan komputasi paralel, dan dapat mengekspresikan hal-hal yang tidak dapat dilakukan oleh satu mesin seragam pun.

Mengapa peneliti peduli dengan batas bawah sirkuit?

Membuktikan bahwa masalah dalam NP memerlukan sirkuit yang sangat besar akan memisahkan kelas kompleksitas dan dapat menyelesaikan P versus NP. Batas bawah diketahui untuk keluarga sirkuit terbatas, tetapi memperluasnya ke sirkuit umum terhalang oleh hambatan formal, menjadikan ini salah satu tantangan terbuka terdalam di bidang ini.