TC (complejidad)

En la ciencia de la computación teórica , y específicamente en la teoría de la complejidad computacional y la complejidad de circuitos , TC (Threshold Circuit) es una clase de complejidad de problemas de decisión que pueden ser reconocidos por circuitos umbral, que son circuitos booleanos con puertas AND , OR y de mayoría , o equivalentemente, puertas umbral . Para cada i fijo , la clase de complejidad TC ⁱ consta de todos los lenguajes que pueden ser reconocidos por una familia de circuitos umbral de profundidad${\displaystyle O(\log ^{i}n)}$, tamaño polinomial y fan-in ilimitado . La clase TC se define mediante

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

La clase fue propuesta en 1988 para formalizar la complejidad computacional de las redes neuronales artificiales . ^{[ 1 ]}

La relación entre la jerarquía TC, NC y AC se puede resumir de la siguiente manera:

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

En particular, sabemos que

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

La primera contención estricta se deriva del hecho de que NC ⁰ no puede calcular ninguna función que dependa de todos los bits de entrada. Por lo tanto, elegir un problema que sea trivialmente de AC ⁰ y que dependa de todos los bits separa las dos clases. (Por ejemplo, considérese la función OR). La contención estricta AC ⁰ ⊊ TC ⁰ se deriva porque se demostró que la paridad y la mayoría ( que están ambas en TC ⁰ ) no están en AC ^{0. [ 2 ] [ 3 ]}

Como consecuencia inmediata de las limitaciones anteriores, tenemos que NC = AC = TC.

• Vollmer, Heribert (1999). Introducción a la complejidad de los circuitos . Berlín: Springer. ISBN 3-540-64310-9.