TC0

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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

Quan hệ với các lớp độ phức tạp khác[sửa | sửa mã nguồn]

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

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

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 \mbox{TC}^0 \subsetneq \mbox{PP}. (Allender (1996), theo Burtschick & Vollmer (1999)).

Chú thích[sửa | sửa mã nguồn]

  1. ^ [1]

Tài liệu tham khảo[sửa | sửa mã nguồn]

  • Allender, E. (1996), A note on uniform circuit lower bounds for the counting hierarchy, “Proceedings 2nd International Computing and Combinatorics Conference (COCOON)”, Springer Lecture Notes in Computer Science 1090: 127–135 
  • 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, Bản mẫu:ECCC 

Liên kết ngoài[sửa | sửa mã nguồn]