ТК (сложность)

В теоретической информатике и, в частности, в теории сложности вычислений и сложности схем , TC — это класс сложности задач принятия решений , которые можно распознать с помощью пороговых схем, которые представляют собой логические схемы с логическими элементами И , ИЛИ и большинства . Для каждого фиксированного i класс сложности TC ^я состоит из всех языков, которые могут быть распознаны семейством пороговых схем глубины $O(\log ^{i}n)$, полиномиальный размер и неограниченное разветвление . Класс TC определяется через

${\mbox{TC}}=\bigcup _{i\geq 0}{\mbox{TC}}^{i}.$

Связь с NC и AC

Взаимосвязь между иерархией TC, NC и AC можно резюмировать следующим образом:

${\mbox{NC}}^{i}\subseteq {\mbox{AC}}^{i}\subseteq {\mbox{TC}}^{i}\subseteq {\mbox{NC}}^{i+1}.$

В частности, мы знаем, что

${\mbox{NC}}^{0}\subsetneq {\mbox{AC}}^{0}\subsetneq {\mbox{TC}}^{0}\subseteq {\mbox{NC}}^{1}.$

Первое строгое сдерживание следует из того, что NC ⁰ не может вычислить какую-либо функцию, которая зависит от всех входных битов. Таким образом, выбирая задачу, которая тривиально относится к AC ⁰ и зависит от всех битов, разделяющих два класса. (Например, рассмотрим функцию ИЛИ.) Строгое сдерживание AC ⁰ ⊊ ТК ⁰ следует, потому что паритет и большинство (которые оба находятся в TC ⁰ ) оказались не в AC ⁰ .

Как непосредственное следствие приведенных выше ограничений, мы имеем NC = AC = TC.

Ссылки

• Воллмер, Гериберт (1999). Введение в сложность схем . Берлин: Шпрингер. ISBN  3-540-64310-9 .