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

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

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

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

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

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

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

Первое строгое включение следует из того факта, что NC ⁰ не может вычислить никакую функцию, которая зависит от всех входных битов. Таким образом, выбор задачи, которая тривиально находится в AC ⁰ и зависит от всех битов, разделяет два класса. (Например, рассмотрим функцию OR.) Строгое включение AC ⁰ ⊊ TC ⁰ следует, поскольку было показано, что четность и большинство (которые оба находятся в TC ⁰ ) не находятся в AC ⁰ . ^{[1] [2]}

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

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