TC0

TC ⁰は、回路の複雑度で使用される複雑度クラスです。これは、 TCクラスの階層の最初のクラスです。

TC ^{0には、定数の深さと多項式サイズを持つ}ブール回路によって決定されるすべての言語が含まれており、無制限のファンインAND ゲート、OR ゲート、NOT ゲート、および多数決ゲートのみが含まれています。同様に、多数決ゲートの代わりにしきい値ゲートを使用することもできます。

TC ⁰には、nビット 数のソート、2つのnビット数の乗算、整数除算^{[1] 、または2種類の括弧を持つ}Dyck言語の認識など、いくつかの重要な問題が含まれています。

TC ^{0 は、} AC ⁰やNC ¹などの他の回路クラスに関連付けることができます。Vollmer 1999 の 126 ページには次のように記載されています。

${\displaystyle {\mathsf {AC}}^{0}\subsetneq {\mathsf {AC}}^{0}[p]\subsetneq {\mathsf {TC}}^{0}\subseteq {\mathsf {NC}}^{1}.}$

Vollmer は、上記の最後の包含が厳密であるかどうかという問題は、「回路の複雑さにおける主要な未解決問題の 1 つ」であると述べています (同上)。

私たちにはそのユニフォームもあります。(Allender 1996、Burtschick 1999 で引用) ${\displaystyle {\mathsf {TC}}^{0}\subsetneq {\mathsf {PP}}}$

一様体の関数バージョンは、射影の合成に関する閉包と、次の関数セット、のいずれかと一致します。^[2]ここで、 、は、および のビット単位の AND です。関数バージョンとは、 FPの関数によって制限され、一様体 に含まれる非負の整数上のすべての関数の集合を意味します。 ${\displaystyle {\mbox{TC}}^{0}}$${\displaystyle \{n+m,n\,{\stackrel {.}{-}}\,m,n\wedge m,\lfloor n/m\rfloor ,2^{\lfloor \log _{2}n\rfloor ^{2}}\}}$${\displaystyle \{n+m,n\,{\stackrel {.}{-}}\,m,n\wedge m,\lfloor n/m\rfloor ,n^{\lfloor \log _{2}m\rfloor }\}}$${\displaystyle n\,{\stackrel {.}{-}}\,m=\max(0,nm)}$${\displaystyle n\wedge m}$${\displaystyle n}$${\displaystyle m}$${\displaystyle f(x_{1},\ldots,x_{n})}$${\displaystyle (y{\text{-番目のビット }}f(x_{1},\ldots ,x_{n}))}$${\displaystyle {\mbox{TC}}^{0}}$

• Allender, E. (1996)。「カウンティング階層の均一回路下限に関する注記」。第 2 回国際コンピューティングおよび組合せ論会議 (COCOON) の議事録。Springer Lecture Notes in Computer Science。第 1090 巻。127 ～ 135 ページ。
• Clote, Peter; Kranakis, Evangelos (2002)。ブール関数と計算モデル。理論計算機科学テキスト。EATCS シリーズ。ベルリン: Springer- Verlag。ISBN 3-540-59436-1.ZBL1016.94046  。​
• Vollmer, Heribert (1999)。回路の複雑さへの入門。統一的なアプローチ。理論計算機科学テキスト。ベルリン: Springer - Verlag。ISBN 3-540-64310-9.ZBL 0931.68055  .
• Burtschick, Hans-Jörg; Vollmer, Heribert (1998). 「Lindström 量指定子とリーフ言語の定義可能性」. International Journal of Foundations of Computer Science . 9 (3): 277–294. doi :10.1142/S0129054198000180. ECCC  TR96-005.

• 複雑動物園: TC0