TC(복잡성)

이론 컴퓨터 과학, 특히 계산 복잡성 이론과 회로 복잡성에서 TC는 임계 회로로 인식할 수 있는 의사결정 문제의 복잡성 등급으로, AND, OR, Major 게이트를 가진 부울 회로가 있다.각 고정 i에 대해 복잡도 클래스 TC는ⁱ $깊이{\displaystyle }$ O${\displaystyle ({\log }^{}}$ ${\displaystyle i^{}}$ ${\displaystyle {}^{}n}$) ${\displaystyle$ O$(\log ^{i}n$ 다항식 크기 및 무한 팬인의 임계값 회로 계열에서 인식할 수 있는 모든 언어로 구성된다.클래스 TC는 다음을 통해 정의된다.

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

NC 및 AC와의 관계

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]null

상기 포함의 즉각적인 결과로서 NC = AC = TC가 있다.null

참조

• Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.