Share to:

AC0

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ú

^ 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. Quyển 57 số 5. New York, NY, USA: ACM. tr. 28:1--28:10. doi:10.1145/1754399.1754401.

x t s Các lớp độ phức tạp quan trọng (thêm)
Các lớp được coi là giải được	DLOGTIME • AC⁰ • ACC⁰ • TC⁰ • 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 hãy giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.