- Source: TC0
TC0 is a complexity class used in circuit complexity. It is the first class in the hierarchy of TC classes.
TC0 contains all languages which are decided by Boolean circuits with constant depth and polynomial size, containing only unbounded fan-in AND gates, OR gates, NOT gates, and majority gates. Equivalently, threshold gates can be used instead of majority gates.
TC0 contains several important problems, such as sorting n n-bit numbers, multiplying two n-bit numbers, integer division or recognizing the Dyck language with two types of parentheses.
Complexity class relations
We can relate TC0 to other circuit classes, including AC0 and NC1; Vollmer 1999 p. 126 states:
A
C
0
⊊
A
C
0
[
p
]
⊊
T
C
0
⊆
N
C
1
.
{\displaystyle {\mathsf {AC}}^{0}\subsetneq {\mathsf {AC}}^{0}[p]\subsetneq {\mathsf {TC}}^{0}\subseteq {\mathsf {NC}}^{1}.}
Vollmer states that the question of whether the last inclusion above is strict is "one of the main open problems in circuit complexity" (ibid.).
We also have that uniform
T
C
0
⊊
P
P
{\displaystyle {\mathsf {TC}}^{0}\subsetneq {\mathsf {PP}}}
. (Allender 1996, as cited in Burtschick 1999).
Basis for uniform TC0
The functional version of the uniform
TC
0
{\displaystyle {\mbox{TC}}^{0}}
coincides with the closure with respect to composition of the projections and one of the following function sets
{
n
+
m
,
n
−
.
m
,
n
∧
m
,
⌊
n
/
m
⌋
,
2
⌊
log
2
n
⌋
2
}
{\displaystyle \{n+m,n\,{\stackrel {.}{-}}\,m,n\wedge m,\lfloor n/m\rfloor ,2^{\lfloor \log _{2}n\rfloor ^{2}}\}}
,
{
n
+
m
,
n
−
.
m
,
n
∧
m
,
⌊
n
/
m
⌋
,
n
⌊
log
2
m
⌋
}
{\displaystyle \{n+m,n\,{\stackrel {.}{-}}\,m,n\wedge m,\lfloor n/m\rfloor ,n^{\lfloor \log _{2}m\rfloor }\}}
. Here
n
−
.
m
=
max
(
0
,
n
−
m
)
{\displaystyle n\,{\stackrel {.}{-}}\,m=\max(0,n-m)}
,
n
∧
m
{\displaystyle n\wedge m}
is a bitwise AND of
n
{\displaystyle n}
and
m
{\displaystyle m}
. By functional version one means the set of all functions
f
(
x
1
,
…
,
x
n
)
{\displaystyle f(x_{1},\ldots ,x_{n})}
over non-negative integers that are bounded by functions of FP and
(
y
-th bit of
f
(
x
1
,
…
,
x
n
)
)
{\displaystyle (y{\text{-th bit of }}f(x_{1},\ldots ,x_{n}))}
is in the uniform
TC
0
{\displaystyle {\mbox{TC}}^{0}}
.
References
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. Vol. 1090. pp. 127–135.
Clote, Peter; Kranakis, Evangelos (2002). Boolean functions and computation models. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 3-540-59436-1. Zbl 1016.94046.
Vollmer, Heribert (1999). Introduction to Circuit Complexity. A uniform approach. Texts in Theoretical Computer Science. Berlin: Springer-Verlag. ISBN 3-540-64310-9. Zbl 0931.68055.
Burtschick, Hans-Jörg; Vollmer, Heribert (1998). "Lindström quantifiers and leaf language definability". International Journal of Foundations of Computer Science. 9 (3): 277–294. doi:10.1142/S0129054198000180. ECCC TR96-005.
External links
Complexity Zoo: TC0