AC0

Sơ đồ mạch AC⁰: n bit đầu vào nằm ở phía dưới và cổng trên tạo ra đầu ra; mạch bao gồm các cổng AND và OR của mỗi fan-in đa thức và độ sâu xen kẽ bị giới hạn bởi một hằng số.

AC⁰ 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 NC⁰ (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 AC⁰ nào.^[1] Do đó, AC⁰ không bằng NC¹, do tồn tại một họ mạch trong NC¹ kiểm tra được tính chẵn lẻ.

Năm 2008, Mark Braverman đã chứng minh các mạch trong AC⁰ 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ú

1. M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17:13–27, 1984.
2. Mark Braverman (2008). "Polylogarithmic independence fools AC0 circuits". J. ACM. Quyển 57 số 5. New York, NY, USA: ACM. tr. 28:1--28:10. doi:10.1145/1754399.1754401.