AC0 là một lớp độ phức tạp trong độ phức tạp mạch. Nó là lớp nhỏ nhất trong cấp bậc AC, bao gồm tất cả các mạch có chiều sâu O(1) và kích thước đa thức, với cổng AND và cổng OR có fan-in (số dữ liệu vào) không giới hạn. (cổng NOT chỉ được sử dụng cho dữ liệu vào). Nó bao hàm lớp NC0 (chỉ cho phép cổng AND và OR với fan-in là hằng số).
Năm 1984, Furst, Saxe, và Sipser chứng minh rằng không thể kiểm tra tính chẵn lẻ của dữ liệu vào bằng bất kì mạch AC0 nào.[1] Do đó, AC0 không bằng NC1, do tồn tại một gia đình các mạch trong NC1 kiểm tra được tính chẵn lẻ.
Năm 2008, Mark Braverman đã chứng minh các mạch trong AC0 không thể phân biệt được phân bố với độ độc lập đa thức của lôgarit của kích thước với phân bố ngẫu nhiên thực sự.[2]
Ghi chú
- ^ M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17:13–27, 1984.
- ^ Mark Braverman (2008). “Polylogarithmic independence fools AC0 circuits”. J. ACM. New York, NY, USA: ACM. 57 (5): 28:1--28:10. doi:10.1145/1754399.1754401.
Các lớp độ phức tạp quan trọng (thêm) |
|---|
| Các lớp được coi là giải được | DLOGTIME • AC0 • ACC0 • TC0 • L • SL • RL • NL • NC • SC • P (P-đầy đủ) • ZPP • RP • BPP • BQP |
|---|
| Các lớp có thể không giải được | UP • NP ( NP-đầy đủ · NP-khó · co-NP · co-NP-đầy đủ) • AM • PH • PP • #P (#P-đầy đủ) • IP • PSPACE (PSPACE-đầy đủ) |
|---|
| Các lớp được coi là không giải được | EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL |
|---|
| Các hệ thống cấp bậc | Cấp bậc đa thức • Cấp bậc hàm mũ • Cấp bậc Grzegorczyk • Cấp bậc số học |
|---|
| Các nhóm các lớp độ phức tạp | DTIME • NTIME • DSPACE • NSPACE • Chứng minh có thể kiểm chứng ngẫu nhiên • Hệ thống chứng minh tương tác |
|---|
| Bài viết này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn. |
