TC0

TC⁰ 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.

TC⁰ 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ố.

TC⁰ 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 ^[1].

Quan hệ với các lớp độ phức tạp khác

Có thể so sánh TC⁰ với các lớp độ phức tạp mạch khác như AC⁰ và NC¹. Theo Vollmer 1999, tr. 126:

${\displaystyle {\mbox{AC}}^{0}\subsetneq {\mbox{AC}}^{0}[p]\subsetneq {\mbox{TC}}^{0}\subseteq {\mbox{NC}}^{1}.}$

Cũng theo Vollmer, liệu TC⁰ có là tập con thực sự của NC¹ 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 ${\displaystyle {\mbox{TC}}^{0}\subsetneq {\mbox{PP}}}$. (Allender (1996), theo Burtschick & Vollmer (1999)).

Chú thích

1. [1]

Tham khảo

• Allender, E. (1996), “Proceedings 2nd International Computing and Combinatorics Conference (COCOON)”, Springer Lecture Notes in Computer Science, 1090: 127–135 |contribution= bị bỏ qua (trợ giúp)
• Vollmer, Heribert (1999), Introduction to Circuit Complexity, Berlin: Springer, ISBN 3-540-64310-9
• Burtschick, Hans-Jörg; Vollmer, Heribert (1999), Lindström Quantifiers and Leaf Language Definability, ECCC TR96-005

Liên kết ngoài

• Bản mẫu:CZoo