TC0

{{DISPLAYTITLE:TC0}}
TC0 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 TC.

TC0 bao gồm tất cả các ngôn ngữ quyết định được bởi mạch lôgic với chiều sâu hằng số và kích thước đa thức, chỉ sử dụng cổng AND, cổng OR, và cổng đa số (kết quả là bit dữ liệu vào phổ biến hơn giữa 0 và 1) với số dữ liệu vào không giới hạn. Một cách tương đương, có thể dùng cổng ngưỡng (số bit dữ liệu vào bằng 1 có vượt quá một ngưỡng cố định hay không) thay vì cổng đa số.

TC0 chứa nhiều bài toán quan trọng, chẳng hạn như sắp xếp n số n bit, và nhân hai số n bit, chia số nguyên .

Quan hệ với các lớp độ phức tạp khác
Có thể so sánh TC0 với các lớp độ phức tạp mạch khác như AC0 và NC1. Theo :
 
Cũng theo Vollmer, liệu TC0 có là tập con thực sự của NC1 là "một trong những bài toán mở chính của độ phức tạp mạch" (cùng vị trí trích dẫn trên).

Ngoài ra, phiên bản đồng dạng (uniform) của . (, theo ).

Chú thích

Tham khảo

Liên kết ngoài

Độ phức tạp mạch
Lớp độ phức tạp