Xem mã nguồn của TC0

{{DISPLAYTITLE:TC<sup>0</sup>}}
'''TC<sup>0</sup>''' 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 (độ phức tạp)|TC]].

TC<sup>0</sup> 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<sup>0</sup> 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 <ref>[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.8882]</ref>.

==Quan hệ với các lớp độ phức tạp khác==
Có thể so sánh TC<sup>0</sup> với các lớp độ phức tạp mạch khác như [[AC0|AC<sup>0</sup>]] và [[NC1 (độ phức tạp)|NC<sup>1</sup>]]. Theo {{harvnb|Vollmer|1999|p=126}}:
<blockquote>
<math>\mbox{AC}^0 \subsetneq \mbox{AC}^0[p] \subsetneq \mbox{TC}^0 \subseteq \mbox{NC}^1. </math>
</blockquote> 
Cũng theo Vollmer, liệu '''TC<sup>0</sup>''' có là tập con thực sự của '''NC<sup>1</sup>''' 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 <math>\mbox{TC}^0 \subsetneq \mbox{PP}</math>. ({{harvtxt|Allender|1996}}, theo {{harvtxt|Burtschick|Vollmer|1999}}).

==Chú thích==
{{Tham khảo}}
==Tham khảo==
*{{chú thích|first1=E.|last1=Allender|contribution=A note on uniform circuit lower bounds for the counting hierarchy|title=Proceedings 2nd International Computing and Combinatorics Conference (COCOON)|volume=1090|journal=Springer Lecture Notes in Computer Science|pages=127&ndash;135|year=1996}}
*{{chú thích| last = Vollmer | first = Heribert | title = Introduction to Circuit Complexity | year = 1999 | publisher = Springer | location = Berlin | isbn = 3-540-64310-9}}
*{{chú thích| last1 = Burtschick | first1 = Hans-Jörg | first2 = Heribert | last2= Vollmer | title = Lindström Quantifiers and Leaf Language Definability | id={{ECCC|1996|96|005}}| year = 1999}}

==Liên kết ngoài==
*{{CZoo|TC<sup>0</sup>|T#tc0}}

{{Lớp độ phức tạp}}

[[Thể loại:Độ phức tạp mạch]]
[[Thể loại:Lớp độ phức tạp]]