Mạch Boolean và Độ phức tạp Mạch

Mạch Boolean tính toán các hàm thông qua mạng lưới các cổng logic, và độ phức tạp mạch đo lường các vấn đề bằng kích thước và độ sâu của các mạch cần thiết để giải quyết chúng, mang đến một cái nhìn song song và định hướng phần cứng về tính toán.

Definition

Mạch Boolean là một đồ thị có hướng không chu trình của các cổng logic tính toán một hàm của các đầu vào nhị phân có độ dài cố định; độ phức tạp mạch nghiên cứu số lượng cổng tối thiểu, độ sâu, hoặc các tài nguyên cấu trúc khác cần thiết để tính toán một họ hàm Boolean cho trước.

Scope

Chủ đề này bao gồm các mạch và công thức Boolean, các thước đo độ phức tạp về kích thước và độ sâu, các mô hình đồng nhất so với không đồng nhất, các lớp độ sâu thấp như NC và AC, mối quan hệ giữa các giới hạn dưới của mạch và sự phân tách các lớp độ phức tạp, cùng với các kết quả giới hạn dưới mang tính bước ngoặt cho các họ mạch bị hạn chế.

Core questions

• Cái nhìn về tính toán theo mạng cổng khác với các máy tuần tự như thế nào?
• Kích thước và độ sâu của mạch đo lường điều gì, và chúng liên quan đến thời gian và tính song song như thế nào?
• Tại sao các giới hạn dưới của mạch là một con đường để phân tách các lớp độ phức tạp?
• Những giới hạn dưới nào đã được biết, và những rào cản nào ngăn chặn các giới hạn mạnh hơn?

Key theories

Tính không đồng nhất và lớp P/poly

Các mạch cho phép một máy khác nhau cho mỗi độ dài đầu vào, tạo ra lớp không đồng nhất P/poly chứa P; việc chỉ ra rằng một vấn đề NP-đầy đủ thiếu các mạch kích thước đa thức sẽ phân tách P khỏi NP, thúc đẩy các giới hạn dưới của mạch.

Các giới hạn dưới cho các mạch bị hạn chế

Các giới hạn dưới mạnh mẽ đã được biết đối với các họ giới hạn, chẳng hạn như kích thước hàm mũ cần thiết cho các mạch độ sâu hằng số tính toán tính chẵn lẻ, mặc dù các giới hạn dưới cho các mạch tổng quát vẫn nằm ngoài tầm với.

Clinical relevance

Mạch là mô hình tự nhiên của phần cứng kỹ thuật số, do đó độ phức tạp mạch cung cấp thông tin cho thiết kế chip và giới hạn của tính toán song song; các lớp độ sâu thấp nắm bắt những gì có thể được tính toán nhanh chóng với nhiều bộ xử lý, và các giới hạn dưới của mạch là một chiến lược chính trong nỗ lực dài hạn nhằm giải quyết các câu hỏi như P so với NP.

History

Shannon đã kết nối đại số Boolean với các mạch chuyển mạch vào năm 1937, và độ phức tạp mạch đã trưởng thành thành một lĩnh vực vào những năm 1980 khi Furst, Saxe, Sipser và những người khác đã chứng minh các giới hạn dưới độ sâu hằng số cho tính chẵn lẻ, và Razborov cùng Smolensky đã phát triển các phương pháp đại số, trước khi rào cản chứng minh tự nhiên tiết lộ lý do tại sao các giới hạn dưới tổng quát lại khó nắm bắt đến vậy.

Key figures

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

Seminal works

• aroraBarak2009
• vollmer1999

Frequently asked questions

Các mạch khác với máy Turing như thế nào?

Máy Turing là một thiết bị duy nhất xử lý các đầu vào thuộc mọi kích cỡ từng bước một, trong khi mạch là một mạng lưới cổng cố định cho một độ dài đầu vào, với một mạch riêng biệt cho mỗi độ dài. Tính không đồng nhất này làm cho mạch trở thành một mô hình tự nhiên của phần cứng và của tính toán song song, và nó có thể thể hiện những điều mà không một máy đồng nhất nào có thể làm được.

Tại sao các nhà nghiên cứu quan tâm đến các giới hạn dưới của mạch?

Việc chứng minh rằng một vấn đề trong NP yêu cầu các mạch rất lớn sẽ phân tách các lớp độ phức tạp và có thể giải quyết vấn đề P so với NP. Các giới hạn dưới đã được biết đối với các họ mạch bị hạn chế, nhưng việc mở rộng chúng sang các mạch tổng quát bị chặn bởi các rào cản hình thức, khiến đây trở thành một trong những thách thức mở sâu sắc nhất trong lĩnh vực này.