TC0

이론 컴퓨터 과학, 특히 계산 복잡도 이론과 회로 복잡도에서 TC⁰(임계 회로, 영어: Threshold Circuit)는 TC 종류의 첫 번째 계층이다. TC⁰는 상수 깊이와 다항식 크기를 가지며, 팬 인(fan-in)이 제한되지 않은 AND 게이트, OR 게이트, NOT 게이트, MAJ 게이트 (또는 이와 동등한 임계 게이트)로만 구성된 불 회로로 결정할 수 있는 모든 언어를 포함한다.

TC⁰는 n개의 n비트 숫자를 정렬하기, 두 개의 n비트 숫자 곱하기, 정수 나눗셈 또는 여러 종류의 괄호를 사용하는 다이크 언어 인식하기와 같은 몇 가지 중요한 문제를 포함한다. 이는 유계 깊이 인공 신경망의 계산 복잡도를 모델링하는 데 흔히 사용되며, 실제로 원래 이 목적으로 제안되었다.

정의

불 회로군(영어: Boolean circuit family)은 불 함수들의 피드포워드 네트워크로 구성된 불 회로의 열 $C_{1},C_{2},C_{3},\dots$ 이다. 이진 언어 $L\in 2^{*}$ 가 TC⁰ 종류에 속한다는 것은 다음을 만족하는 불 회로군 $C_{1},C_{2},C_{3},\dots$ 가 존재한다는 의미이다.

다항식 함수 $p$ 와 상수 $d$ 가 존재한다.
각 $C_{n}$ 은 최대 $d$ 개의 층에 있는 최대 $p(n)$ 개의 팬 인(fan-in) 제한이 없는 AND, OR, NOT 및 MAJ 게이트로 구성된다.
모든 $x\in 2^{n}$ 에 대하여, $x\in L$ 일 필요충분조건은 $C_{n}(x)=1$ 이다.

동등하게, MAJ 게이트 대신 다항식으로 유계된 정수 가중치와 임계값을 가진 임계 게이트를 사용할 수 있다. k개의 입력을 가진 임계 게이트는 가중치 목록 $w_{1},\dots ,w_{k}$ 와 단일 임계값 $\theta$ 로 정의된다. 이진 입력 $x_{1},\dots ,x_{k}$ 가 주어지면, $\sum _{i}w_{i}x_{k}>\theta$ 이면 $+1$ 을 출력하고, 그렇지 않으면 $-1$ 을 출력한다. 임계 게이트는 인공 뉴런이라고도 한다.

가중치와 임계값이 $[-M,+M]$ 이내로 유계된 AND, OR, NOT 및 임계 게이트로 구성된 불 회로가 주어졌을 때, 만약 네트워크에 이진 입력의 부정 $\neg x_{1},\dots ,\neg x_{k}$ 를 함께 제공한다면, 동일한 깊이, 각 층의 게이트 수를 최대 두 배로 늘리고, 가중치를 $[0,+M]$ 이내로, 임계값을 $[-M,+M]$ 이내로 유지하면서 AND, OR 및 임계 게이트만 사용하여 동일한 입출력 함수를 계산하는 네트워크로 변환할 수 있다. 따라서 TC⁰는 다음과 같은 조건을 만족하는 불 회로군 $C_{1},C_{2},C_{3},\dots$ 에 의해 결정되는 언어로도 정의할 수 있다.

다항식 함수 $p$ 와 상수 $d$ 가 존재한다.
각 $C_{n}$ 은 최대 $d$ 개의 층에 있는 최대 $p(n)$ 개의 임계 게이트로 구성되며, 가중치는 음수가 아닌 정수, 임계값은 정수이고, 가중치와 임계값 모두 $\pm p(n)$ 이내로 유계된다.
모든 $x\in 2^{n}$ 에 대하여, $x\in L$ 일 필요충분조건은 $C_{n}(x)=1$ 이다.

본 문서에서는 기본적으로 AND, OR, NOT, 임계 게이트의 수가 다항식 개수이고, 정수 가중치와 임계값에 다항식 유계가 있는 불 회로를 고려한다. 가중치와 임계값에 대한 다항식 유계는 ${\mathsf {TC}}^{0}$ 종류를 변경하지 않고도 완화할 수 있다.

산술 회로 복잡도 이론에서 ${\mathsf {TC}}^{0}$ 은 $\mathrm {sign} \circ f_{n}$ 의 상으로 정의되는 언어의 종류로 동등하게 특성화할 수 있다. 여기서 각 $f_{n}:\{0,1\}^{n}\to \mathbb {Z}$ 는 + 및 × 게이트와 $\{-1,0,+1\}$ 상수를 가진, 다항식 크기의 상수 깊이, 팬 인 제한이 없는 산술 회로로 계산된다.

복잡도 종류 간의 관계

컴퓨터 과학의 미해결 문제

{\mathsf {TC}}^{0}{\overset {?}{=}}{\mathsf {NC}}^{1}

(더 많은 컴퓨터 과학의 미해결 문제 보기)

TC⁰를 AC⁰ 및 NC¹을 포함한 다른 회로 종류와 다음과 같이 연관 지을 수 있다.

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

${\mathsf {TC}}^{0}\subseteq {\mathsf {NC}}^{1}$ 이 진부분집합인지 여부는 "회로 복잡도 분야의 주요 미해결 문제 중 하나"이다. 사실 ${\mathsf {TC}}^{0}\subseteq {\mathsf {P/poly}}$ 가 진부분집합인지조차 미해결 문제이다! 이는 어떤 면에서 놀라운 일이 아닌데, ${\mathsf {TC}}^{0}$ 에 암호학적으로 안전한 유사난수 생성기가 존재한다고 가정할 때(이는 블럼 정수의 인수분해가 어렵다는, 즉 $2^{{\mathsf {poly}}(n)}$ 크기의 회로가 필요하다는 가정하에 명시적으로 구성됨), ${\mathsf {TC}}^{0}\subsetneq {\mathsf {P/poly}}$ 를 증명할 자연적 증명이 존재하지 않기 때문이다. 더 일반적으로, 무작위성과 난해성은 밀접하게 관련되어 있음이 밝혀졌다. ${\mathsf {NEXP}}\subseteq {\mathsf {TC}}^{0}$ 인지 여부도 미해결 문제이다. 실제로 ${\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}$ 임은 2011년에야 증명되었다.

비균일(non-uniform) ${\mathsf {TC}}^{0}$ 와 ${\mathsf {ACC}}^{0}$ 은 튜링 기계로 계산 불가능한 함수를 계산할 수 있으므로, ${\mathsf {TC}}^{0}\not \subseteq {\mathsf {NEXP}}$ 와 ${\mathsf {ACC}}^{0}\not \subseteq {\mathsf {NEXP}}$ 인 것은 확실하다. 2011년의 결과는 단순히 ${\mathsf {ACC}}^{0}$ 와 ${\mathsf {NEXP}}$ 가 서로 비교 불가능한 종류임을 보여준다. ${\mathsf {TC}}^{0}$ 와 ${\mathsf {NEXP}}$ 또한 서로 비교 불가능한지 여부가 미해결 문제이다.

비결정적 시간 계층 정리가 ${\mathsf {NP}}\subsetneq {\mathsf {NEXP}}$ 임을 증명하지만, 두 복잡도 종류는 모두 균일(uniform)하며, 이는 단일 튜링 기계가 임의의 입력 길이에 대한 문제를 해결할 책임이 있음을 의미한다. 반면 ${\mathsf {TC}}^{0}$ 회로군은 비균일할 수 있는데, 이는 유계 깊이와 ${\mathsf {poly}}(n)$ 크기를 가진 모든 $2^{{\mathsf {poly}}(n)}$ 개의 가능한 불 회로를 전수 조사한 다음, 회로가 올바른지 확인하기 위해 $2^{n}$ 개의 모든 가능한 입력을 검사하는 것 외에 올바른 회로를 찾기 위한 좋은 알고리즘이 없을 수도 있음을 의미한다.

${\mathsf {TC}}^{0}={\mathsf {NC}}^{1}$ 이라면 모든 $\epsilon >0$ 에 대해, 불 수식 평가(Boolean Formula Evaluation) 문제를 해결하는 $O(n^{1+\epsilon })$ 개의 게이트를 가진 ${\mathsf {TC}}^{0}$ 회로군이 존재함이 증명되었다. 따라서 어떠한 초선형(superlinear) 유계라도 ${\mathsf {TC}}^{0}\neq {\mathsf {NC}}^{1}$ 임을 증명하기에 충분하다.

균일 TC⁰

DLOGTIME-균일 ${\mathsf {TC}}^{0}$ 은 다수결(Majority) 양화사가 있는 1차 논리와 동등하기 때문에 ${\mathsf {FOM}}$ 이라고도 알려져 있다. 구체적으로, $x_{1},x_{2},\dots ,x_{n}$ 불 변수를 취하는 논리식이 주어졌을 때, 다수결 양화사 $M$ 은 다음과 같이 사용된다. 정확히 하나의 자유 변수 $\phi (x)$ 를 가진 논리식이 주어지면, 양화된 $Mx\phi (x)$ 는 $i\in 1:n$ 의 절반 이상에 대해 $\phi (x_{i})$ 가 참일 경우에만 참이다. 정수 나눗셈( $n$ 비트 정수 $x,y$ 가 주어졌을 때 $\lfloor x/y\rfloor$ 찾기), 거듭제곱( $n$ 비트 정수 $x$ 와 $O(\ln(n))$ 비트 정수 $k$ 가 주어졌을 때 $x^{k}$ 찾기), 반복 곱셈( $n$ 개의 $n$ 비트 정수 곱하기)은 모두 DLOGTIME-균일 ${\mathsf {TC}}^{0}$ 에 속한다. 이는 보통 ${\mathsf {TC}}^{0}$ 에 적절한 균일성 수준으로 간주된다. 구체적으로, P는 보통 ${\mathsf {TC}}^{0}$ 보다 강하다고 추측되는 반면, DLOGTIME은 어떤 의미에서 강도가 동등하다고 추측되므로, ${\mathsf {TC}}^{0}$ 의 균일성을 고려할 때는 보통 DLOGTIME-균일성이 가정된다.

0-1 행렬의 퍼머넌트는 균일 ${\mathsf {TC}}^{0}$ 에 속하지 않는다.

균일 ${\mathsf {TC}}^{0}\subsetneq {\mathsf {PP}}$ 이다.

균일 TC⁰의 함수 버전은 사영(projection) 및 다음 함수 집합 중 하나 $\{n+m,n\,{\stackrel {.}{-}}\,m,n\wedge m,\lfloor n/m\rfloor ,2^{\lfloor \log _{2}n\rfloor ^{2}}\}$ , $\{n+m,n\,{\stackrel {.}{-}}\,m,n\wedge m,\lfloor n/m\rfloor ,n^{\lfloor \log _{2}m\rfloor }\}$ 에 대한 합성(composition)에 대해 닫혀 있는 것과 일치한다. 여기서 $n\,{\stackrel {.}{-}}\,m=\max(0,n-m)$ 이고, $n\wedge m$ 은 $n$ 과 $m$ 의 비트 단위 AND이다. 함수 버전이란 FP의 함수들로 유계되고 $(f(x_{1},\ldots ,x_{n}){\text{의 }}y{\text{번째 비트}})$ 가 균일 TC⁰에 속하는, 음이 아닌 정수 위의 모든 함수 $f(x_{1},\ldots ,x_{n})$ 의 집합을 의미한다.

미세 구조

TC⁰는 최대 1층, 2층 등을 필요로 하는 언어의 계층으로 더 세분화될 수 있다. ${\mathsf {TC}}_{d}^{0}$ 를 최대 깊이 $d$ 인 임계 회로군에 의해 결정 가능한 언어의 종류라고 하자: ${\mathsf {TC}}_{1}^{0}\subset {\mathsf {TC}}_{2}^{0}\subset \cdots \subset {\mathsf {TC}}^{0}=\bigcup _{d=1}^{\infty }{\mathsf {TC}}_{d}^{0}$ 계층은 훨씬 더 세밀하게 나뉠 수 있다.

MAJ 대 임계값

MAJ 게이트는 때때로 가중치가 없는 임계 게이트라고 불린다. 이들은 균일 다항식 오버헤드 내에서 동등하다. 상세히 설명하면:

MAJ 게이트는 모든 가중치가 1이고 임계값이 팬 인의 $1/2$ 인 임계 게이트이다.
다항식 정수 가중치와 임계값을 가진 임계 게이트를 포함하는 다항식 크기의 회로는 동일한 깊이의 다항식 크기 회로로 변환될 수 있다. 구체적으로, 가중치는 입력 회로를 복제하여 시뮬레이션할 수 있고, 임계값은 상수 참/거짓 입력을 복제하여 시뮬레이션할 수 있다.

더 나아가, 임의의(제한 없는) 정수 가중치와 임계값을 가진 단일 $n$ -입력 임계 게이트가 주어졌을 때, ${\mathsf {poly}}(n)$ 개의 AND, OR, NOT 및 MAJ 게이트를 사용하여 깊이 2 회로를 구성하는 명시적 알고리즘이 존재한다. 따라서 모든 다항식 크기, 깊이 $d$ 의 임계 회로는 깊이 $d+1$ 의 다항식 크기 다수결 회로로 균일하게 시뮬레이션될 수 있다.

분리 정리로서, 아래 정의된 $n$ -입력 불 내적(IP) 함수는 3개의 층과 $O(n)$ 개의 게이트를 가진 다수결 회로로는 계산 가능하지만, 2개의 층과 ${\mathsf {poly}}(n)$ 개의 게이트를 가진 임계 회로로는 계산 불가능함이 알려져 있다.^{: Section 11.10.2}

임의의 임계 게이트

고정된 $n$ 에 대해, 임계 논리 소자로 계산 가능한 불 함수는 유한하기 때문에, 모든 $w_{1},\dots ,w_{n},\theta$ 를 정수로 설정하는 것이 가능하다. $W(n)$ 을 가능한 모든 $n$ 변수의 실수 임계 함수가 절댓값 $\leq W$ 인 정수 가중치를 사용하여 실현될 수 있는 가장 작은 수 $W$ 라고 하자. 다음이 알려져 있다. ${\frac {1}{2}}n\log n-2n+o(n)\leq \log _{2}W(n)\leq {\frac {1}{2}}n\log n-n+o(n)$ 문헌 고찰은^{: Section 11.10}을 참조하라.

때때로 깊이 $d$ 인 다항식 유계 가중치와 임계값의 종류는 ${\widehat {\mathsf {LT}}}_{d}:={\mathsf {TC}}_{d}^{0}$ 로 표기하고, 가중치와 임계값이 제한 없는 경우("큰 가중치 임계 회로")는 ${\mathsf {LT}}_{d}$ 로 표기한다. 이는 실수값 활성화 함수를 가진 신경망을 형식화한다.

앞서 언급했듯이, 모든 다항식 크기, 깊이 $d$ 의 임계 회로는 깊이 $d+1$ 의 다항식 크기 다수결 회로로 균일하게 시뮬레이션될 수 있다. 따라서 ${\mathsf {TC}}_{d}^{0}\subset {\mathsf {LT}}_{d}\subset {\mathsf {TC}}_{d+1}^{0}$ 이다. ${\mathsf {TC}}_{2}^{0}\subsetneq {\mathsf {LT}}_{2}$ 임이 증명되었다.

시그모이드 함수 $\sigma$ 를 허용하는 것은 능력을 증가시키지 않는데, 즉, 가중치가 다항식 유계라고 가정할 때 모든 $d\geq 1$ 에 대해 ${\mathsf {TC}}_{d}^{0}={\mathsf {TC}}_{d}^{0}(\sigma )$ 이다.

확률적 버전

P 종류에 확률적 버전인 BPP가 있는 것처럼, ${\mathsf {TC}}^{0}$ 에는 확률적 버전인 ${\mathsf {RTC}}^{0}$ 가 있다. 이는 다항식 확률적으로 결정 가능한 언어의 종류로 정의된다.

$C_{1},C_{2},C_{3},\dots$ 를 두 종류의 입력을 받는 불 회로군이라고 하자. 주어진 회로 $C_{n}$ 은 결정론적 입력 $x_{1},\dots ,x_{n}$ 과 $m={\mathsf {poly}}(n)$ 인 무작위 입력 $y_{1},\dots ,y_{m}$ 을 받는다. 무작위 입력은 모든 $2^{m}$ 가능성에서 균등하게 샘플링된다.

언어 $L\subset 2^{*}$ 가 해당 회로군에 의해 다항식 확률적으로 결정된다는 것은, 각 $x\in 2^{n}$ 에 대해, $x\in L$ 이면 $C_{n}(x,y)=+1$ 일 확률이 최소 ${\frac {1}{2}}+{\frac {1}{{\mathsf {poly}}(n)}}$ 이고, $x\not \in L$ 이면 $C_{n}(x,y)=+1$ 일 확률이 최대 ${\frac {1}{2}}-{\frac {1}{{\mathsf {poly}}(n)}}$ 임을 의미한다.

유사하게, (피드포워드) 볼츠만 머신은 유계 신뢰할 수 없는 임계 단위를 가진 ${\mathsf {RTC}}^{0}$ 회로로 모델링되었다. 즉, 각 임계 단위는 독립적으로 무작위로, 유계 확률 $\epsilon <1/2$ 로 잘못된 출력을 낼 수 있다.

때때로 이 종류는 BPP와의 더 밀접한 유추를 위해 ${\mathsf {BPTC}}^{0}$ 라고도 불린다. 이 정의에서, $C_{n}(x,y)=+1$ 일 확률은 $x\in L$ 일 때 최소 ${\frac {2}{3}}$ 이고, $x\not \in L$ 일 때 최대 ${\frac {1}{3}}$ 이다. 여러 번 샘플링한 후 다수결 의견을 취하는 표준 기법에 의해, 모든 $d$ 층 ${\mathsf {RTC}}^{0}$ 회로는 $(d+1)$ 층 ${\mathsf {BPTC}}^{0}$ 회로로 변환될 수 있다.

계층

${\textstyle {\mathsf {TC}}_{1}^{0}\subset {\mathsf {TC}}_{2}^{0}\subset \cdots \subset {\mathsf {TC}}^{0}=\bigcup _{d=1}^{\infty }{\mathsf {TC}}_{d}^{0}}$ 인 것과 유사하게, ${\mathsf {RTC}}^{0}$ 도 다음과 같이 나눌 수 있다. ${\mathsf {RTC}}_{1}^{0}\subset {\mathsf {RTC}}_{2}^{0}\subset \cdots \subset {\mathsf {RTC}}^{0}=\bigcup _{d=1}^{\infty }{\mathsf {RTC}}_{d}^{0}$ 정의에 의해 ${\mathsf {TC}}_{d}^{0}\subset {\mathsf {RTC}}_{d}^{0}$ 이다. 더 나아가, ${\mathsf {RTC}}_{d}^{0}\subset {\mathsf {TC}}_{d+1}^{0}$ 이므로, 전체 계층이 존재한다: ${\mathsf {TC}}_{1}^{0}\subset {\mathsf {RTC}}_{1}^{0}\subset {\mathsf {TC}}_{2}^{0}\subset {\mathsf {RC}}_{2}^{0}\subset \cdots \subset {\mathsf {TC}}^{0}={\mathsf {RTC}}^{0}$ 유사하게, 유계 신뢰할 수 없는 임계 단위를 허용할 때, ${\mathsf {RTC}}_{d}^{0}$ 회로는 원본 회로의 여러 복사본을 병렬로 실행하여(각각 무작위 입력에 대한 고정된 선택, 즉 하드코딩된 어드바이스를 가짐) 그 출력에 대해 다수결을 취함으로써 ${\mathsf {TC}}_{d+1}^{0}$ 회로로 변환될 수 있다. 최소한 하나의 어드바이스가 존재한다는 것은 헤프딩 부등식에 의해, 중간값 트릭과 본질적으로 동일한 논리로 증명된다. 이 논리는 단순한 존재 증명이며, 따라서 ${\mathsf {TC}}^{0}$ 에 있어 중요한 방식의 균일성을 갖지 못하는데, 이는 브루트 포스 열거 외에는 어드바이스를 발견하기 위한 알고리즘을 제공하지 않기 때문이다.

유사하게, ${\mathsf {RTC}}^{0}/{\mathsf {poly}}={\mathsf {TC}}^{0}/{\mathsf {poly}}$ 이다.

$\oplus$ 를 패리티 함수 또는 XOR 함수라고 정의하자. 그러면 다음 두 분리 정리가 성립한다.

${\mathsf {RTC}}_{1}^{0}\subsetneq {\mathsf {TC}}_{2}^{0}$ : 패리티 함수 $\oplus$ 는 ${\mathsf {TC}}_{2}^{0}$ 에 속하지만, ${\mathsf {RTC}}_{1}^{0}$ 에는 속하지 않는다.
${\mathsf {TC}}_{2}^{0}\subsetneq {\mathsf {RTC}}_{2}^{0}$ : 불 내적 함수(IP)는 ${\mathsf {RTC}}_{2}^{0}$ 에 속하지만 ${\mathsf {TC}}_{2}^{0}$ 에는 속하지 않으며, 여기서 $\mathrm {IP} _{n}\left(x_{1},\ldots ,x_{n},x_{1}^{\prime },\ldots ,x_{n}^{\prime }\right)=\bigoplus _{i=1}^{n}\mathrm {AND} \left(x_{i},x_{i}^{\prime }\right)$

내적 함수는 정밀한 의미에서 ${\mathsf {TC}}_{2}^{0}$ 의 범위를 벗어난다:^{: Section 11.10.2}

$\mathrm {IP} _{n}$ 을 계산하는 깊이 2 임계 회로의 하단 게이트 가중치가 다항식이면, 모든 $\epsilon >0$ 에 대해, 충분히 큰 모든 $n$ 에 대해 $\mathrm {IP} _{n}$ 은 $\geq 2^{(1/2-\epsilon )n}$ 개의 게이트를 필요로 한다.
$\mathrm {IP} _{n}$ 을 계산하는 깊이 2 임계 회로의 상단 게이트 가중치가 최대 $2^{o\left(n^{1/3}\right)}$ 이면, 상단 게이트는 최소 $2^{\Omega \left(n^{1/3}\right)}$ 의 팬 인을 가져야 한다.
$\mathrm {IP} _{n}$ 을 계산하는 깊이 2 임계 회로의 하단 게이트 가중치가 $2^{n/3}$ 을 초과하지 않으면, 상단 게이트는 최소 $2^{\Omega (n)}$ 의 팬 인을 가져야 한다.

계층이 얼마나 많은 수준을 갖는지는 미해결 문제이다. ${\mathsf {TC}}^{0}={\mathsf {TC}}_{3}^{0}$ 와 같이 계층이 붕괴되는지 여부도 미해결 문제이다. 사실 ${\mathsf {LT}}_{2}^{0}$ 에 대한 지수 하단 유계는 아직 없다. 따라서 하물며 깊이 3 다항식 크기 다수결 회로에 대한 지수 하단 유계도 아직 없다. 1층에 AND 게이트만 포함하거나 제한된 팬 인 게이트만 포함하는 등의 추가적인 제한이 가해지면 지수 하단 유계가 존재한다.^{: Section 11.10.3}

단조(monotone) ${\mathsf {TC}}^{0}$ (즉, 불 부정이 없는 ${\mathsf {TC}}^{0}$ )에 대한 계층은 강력하게 분리된다. 구체적으로, 각 $d$ 에 대해, 단지 $O(n)$ 개의 AND 및 OR 게이트를 사용하는 깊이 $d$ 회로군에 의해 결정 가능하지만, 단조 ${\mathsf {TC}}_{d-1}^{0}$ 로는 계산하기 위해 지수 크기를 필요로 하는 언어가 구성되었다.

게이트 수에 대한 다항식 유계가 완화되면 ${\mathsf {TC}}_{3}^{0}$ 는 매우 강력해진다. 구체적으로, ${\mathsf {ACC}}^{0}$ 에 속하는 모든 언어는 ${\mathsf {TC}}_{3}^{0}$ 회로군(다수결 게이트 사용)에 의해 결정될 수 있는데, 단지 준다항식 개수의 게이트를 사용한다(다항식 대신). 이 결과는 ${\mathsf {AC}}^{0}$ 의 3개 층으로 계산 가능하지만 ${\mathsf {TC}}_{2}^{0}$ (다수결 게이트 사용)에 대해서는 최소한 지수 개수의 게이트를 필요로 하는 함수가 존재한다는 점에서 최적이다.

각주

1 2 Hesse, William; Allender, Eric; Mix Barrington, David (2002). “Uniform constant-depth threshold circuits for division and iterated multiplication”. 《Journal of Computer and System Sciences》 65 (4): 695–716. doi:10.1016/S0022-0000(02)00025-9.
↑ Parberry, Ian; Schnitger, Georg (1988년 6월 1일). “Parallel computation with threshold functions”. 《Journal of Computer and System Sciences》 36 (3): 278–302. doi:10.1016/0022-0000(88)90030-X. ISSN 0022-0000.
↑ Agrawal, Manindra; Allender, Eric; Datta, Samir (4월 2000). “On TC0, AC0, and Arithmetic Circuits” (영어). 《Journal of Computer and System Sciences》 60 (2): 395–421. doi:10.1006/jcss.1999.1675.
1 2 Vollmer, Heribert (1998). 《Introduction to circuit complexity. A uniform approach》. Texts in Theoretical Computer Science. Berlin: Springer-Verlag. 126쪽. ISBN 3-540-64310-9. Zbl 0931.68055.
↑ Naor, Moni; Reingold, Omer (3월 2004). “Number-theoretic constructions of efficient pseudo-random functions” (영어). 《Journal of the ACM》 51 (2): 231–262. doi:10.1145/972639.972643. ISSN 0004-5411.
↑ Hatami, Pooya; Hoza, William M.; Tal, Avishay; Tell, Roei (2월 2022). 〈Fooling Constant-Depth Threshold Circuits (Extended Abstract)〉. 《2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)》. IEEE. 104–115쪽. doi:10.1109/FOCS52979.2021.00019. ISBN 978-1-6654-2055-6.
↑ Williams, Ryan (6월 2011). 〈Non-uniform ACC Circuit Lower Bounds〉. 《2011 IEEE 26th Annual Conference on Computational Complexity》. 115–125쪽. doi:10.1109/CCC.2011.36. ISBN 978-1-4577-0179-5.
↑ Allender, Eric; Koucký, Michal (3월 2010). “Amplifying lower bounds by means of self-reducibility” (영어). 《Journal of the ACM》 57 (3): 1–36. doi:10.1145/1706591.1706594. ISSN 0004-5411.
↑ Mix Barrington, David A.; Immerman, Neil; Straubing, Howard (1990년 12월 1일). “On uniformity within NC1”. 《Journal of Computer and System Sciences》 41 (3): 274–306. doi:10.1016/0022-0000(90)90022-D. ISSN 0022-0000.
↑ Hesse, William (2001), 〈Division Is In Uniform TC0〉 (영어), Orejas, Fernando; Spirakis, Paul G.; van Leeuwen, Jan (편집), 《Automata, Languages and Programming》, Lecture Notes in Computer Science 2076, Berlin, Heidelberg: Springer Berlin Heidelberg, 104–114쪽, doi:10.1007/3-540-48224-5_9, ISBN 978-3-540-42287-7, 2025년 3월 19일에 확인함
↑ Santhanam, Rahul; Williams, Ryan (2014년 6월 1일). “On Uniformity and Circuit Lower Bounds” (영어). 《Computational Complexity》 23 (2): 177–205. doi:10.1007/s00037-014-0087-y. hdl:20.500.11820/d254202f-5539-45ba-ba25-cfe680aa46e9. ISSN 1420-8954.
↑ Allender, Eric (1999). “The permanent requires large uniform threshold circuits” (영어). 《Chicago Journal of Theoretical Computer Science》 5 (1): 1–19. doi:10.4086/cjtcs.1999.007. ISSN 1073-0486.
↑ 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 1090. 127–135쪽. As cited in 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.
↑ Volkov, Sergey. (2016). “Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions, dissertation”. arXiv:1611.04843 [cs.CC].
1 2 Goldmann, Mikael; Håstad, Johan; Razborov, Alexander (1992년 12월 1일). “Majority gates vs. general weighted threshold gates” (영어). 《Computational Complexity》 2 (4): 277–300. doi:10.1007/BF01200426. ISSN 1420-8954.
↑ Goldmann, Mikael; Karpinski, Marek (2월 1998). “Simulating Threshold Circuits by Majority Circuits” (영어). 《SIAM Journal on Computing》 27 (1): 230–246. doi:10.1137/S0097539794274519. ISSN 0097-5397.
1 2 3 4 Jukna, Stasys (2012). 《Boolean Function Complexity: Advances and Frontiers》. Algorithms and Combinatorics. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-642-24507-7.
↑ Alon, Noga; Vũ, Văn H (1997년 7월 1일). “Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs”. 《Journal of Combinatorial Theory, Series A》 79 (1): 133–160. doi:10.1006/jcta.1997.2780. ISSN 0097-3165.
1 2 Šíma, Jiří; Orponen, Pekka (2003년 12월 1일). “General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results” (영어). 《Neural Computation》 15 (12): 2727–2778. doi:10.1162/089976603322518731. ISSN 0899-7667. PMID 14629867.
↑ Maass, W.; Schnitger, G.; Sontag, E.D. (1991). 〈On the computational power of sigmoid versus Boolean threshold circuits〉. 《[1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science》. IEEE Comput. Soc. Press. 767–776쪽. doi:10.1109/SFCS.1991.185447. ISBN 978-0-8186-2445-2.
1 2 3 4 5 6 7 Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György (4월 1993). “Threshold circuits of bounded depth” (영어). 《Journal of Computer and System Sciences》 46 (2): 129–154. doi:10.1016/0022-0000(93)90001-D.
1 2 Parberry, Ian; Schnitger, Georg (1989년 1월 1일). “Relating Boltzmann machines to conventional models of computation”. 《Neural Networks》 2 (1): 59–67. doi:10.1016/0893-6080(89)90015-4. ISSN 0893-6080.
↑ Ajtai, Miklos; Ben-Or, Michael (1984). 〈A theorem on probabilistic constant depth Computations〉 (영어). 《Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84》. ACM Press. 471–474쪽. doi:10.1145/800057.808715. ISBN 978-0-89791-133-7.
↑ Forster, Jürgen; Krause, Matthias; Lokam, Satyanarayana V.; Mubarakzjanov, Rustam; Schmitt, Niels; Simon, Hans Ulrich (2001), 〈Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity〉, Hariharan, Ramesh; Vinay, V.; Mukund, Madhavan (편집), 《FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science》 2245, Berlin, Heidelberg: Springer Berlin Heidelberg, 171–182쪽, doi:10.1007/3-540-45294-x_15, ISBN 978-3-540-43002-5, 2025년 3월 19일에 확인함
↑ Håstad, Johan; Goldmann, Mikael (6월 1991). “On the power of small-depth threshold circuits” (영어). 《Computational Complexity》 1 (2): 113–129. doi:10.1007/BF01272517. ISSN 1016-3328.
↑ Allender, E. (10월 1989). 〈A note on the power of threshold circuits〉. 《30th Annual Symposium on Foundations of Computer Science》. 580–584쪽. doi:10.1109/SFCS.1989.63538. ISBN 0-8186-1982-1.
↑ Yao, Andrew Chi-Chih (1990). 〈On ACC and threshold circuits〉. 《31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22–24, 1990, Volume II》. IEEE Computer Society. 619–627쪽. doi:10.1109/FSCS.1990.89583. ISBN 0-8186-2082-X.
↑ Sherstov, Alexander A. (2009), “Separating $AC 0$ from depth-2 majority circuits”, 《SIAM Journal on Computing》 38 (6): 2113–2129, doi:10.1137/08071421X, MR 2491551

더 읽어보기

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.
Parberry, Ian; Garey, Michael R.; Meyer, Albert (1994년 7월 27일). 《Circuit Complexity and Neural Networks》 (영어). The MIT Press. doi:10.7551/mitpress/1836.001.0001. ISBN 978-0-262-28124-9.

외부 링크

컴플렉시티 주: TC⁰

[:4-1] 1 2 Hesse, William; Allender, Eric; Mix Barrington, David (2002). “Uniform constant-depth threshold circuits for division and iterated multiplication”. 《Journal of Computer and System Sciences》 65 (4): 695–716. doi:10.1016/S0022-0000(02)00025-9.

[2] Parberry, Ian; Schnitger, Georg (1988년 6월 1일). “Parallel computation with threshold functions”. 《Journal of Computer and System Sciences》 36 (3): 278–302. doi:10.1016/0022-0000(88)90030-X. ISSN 0022-0000.

[3] Agrawal, Manindra; Allender, Eric; Datta, Samir (4월 2000). “On TC0, AC0, and Arithmetic Circuits” (영어). 《Journal of Computer and System Sciences》 60 (2): 395–421. doi:10.1006/jcss.1999.1675.

[voll126-4] 1 2 Vollmer, Heribert (1998). 《Introduction to circuit complexity. A uniform approach》. Texts in Theoretical Computer Science. Berlin: Springer-Verlag. 126쪽. ISBN 3-540-64310-9. Zbl 0931.68055.

[5] Naor, Moni; Reingold, Omer (3월 2004). “Number-theoretic constructions of efficient pseudo-random functions” (영어). 《Journal of the ACM》 51 (2): 231–262. doi:10.1145/972639.972643. ISSN 0004-5411.

[6] Hatami, Pooya; Hoza, William M.; Tal, Avishay; Tell, Roei (2월 2022). 〈Fooling Constant-Depth Threshold Circuits (Extended Abstract)〉. 《2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)》. IEEE. 104–115쪽. doi:10.1109/FOCS52979.2021.00019. ISBN 978-1-6654-2055-6.

[7] Williams, Ryan (6월 2011). 〈Non-uniform ACC Circuit Lower Bounds〉. 《2011 IEEE 26th Annual Conference on Computational Complexity》. 115–125쪽. doi:10.1109/CCC.2011.36. ISBN 978-1-4577-0179-5.

[8] Allender, Eric; Koucký, Michal (3월 2010). “Amplifying lower bounds by means of self-reducibility” (영어). 《Journal of the ACM》 57 (3): 1–36. doi:10.1145/1706591.1706594. ISSN 0004-5411.

[9] Mix Barrington, David A.; Immerman, Neil; Straubing, Howard (1990년 12월 1일). “On uniformity within NC1”. 《Journal of Computer and System Sciences》 41 (3): 274–306. doi:10.1016/0022-0000(90)90022-D. ISSN 0022-0000.

[10] Hesse, William (2001), 〈Division Is In Uniform TC0〉 (영어), Orejas, Fernando; Spirakis, Paul G.; van Leeuwen, Jan (편집), 《Automata, Languages and Programming》, Lecture Notes in Computer Science 2076, Berlin, Heidelberg: Springer Berlin Heidelberg, 104–114쪽, doi:10.1007/3-540-48224-5_9, ISBN 978-3-540-42287-7, 2025년 3월 19일에 확인함

[11] Santhanam, Rahul; Williams, Ryan (2014년 6월 1일). “On Uniformity and Circuit Lower Bounds” (영어). 《Computational Complexity》 23 (2): 177–205. doi:10.1007/s00037-014-0087-y. hdl:20.500.11820/d254202f-5539-45ba-ba25-cfe680aa46e9. ISSN 1420-8954.

[12] Allender, Eric (1999). “The permanent requires large uniform threshold circuits” (영어). 《Chicago Journal of Theoretical Computer Science》 5 (1): 1–19. doi:10.4086/cjtcs.1999.007. ISSN 1073-0486.

[13] 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 1090. 127–135쪽. As cited in 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.

[14] Volkov, Sergey. (2016). “Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions, dissertation”. arXiv:1611.04843 [cs.CC].

[:5-15] 1 2 Goldmann, Mikael; Håstad, Johan; Razborov, Alexander (1992년 12월 1일). “Majority gates vs. general weighted threshold gates” (영어). 《Computational Complexity》 2 (4): 277–300. doi:10.1007/BF01200426. ISSN 1420-8954.

[16] Goldmann, Mikael; Karpinski, Marek (2월 1998). “Simulating Threshold Circuits by Majority Circuits” (영어). 《SIAM Journal on Computing》 27 (1): 230–246. doi:10.1137/S0097539794274519. ISSN 0097-5397.

[:1-17] 1 2 3 4 Jukna, Stasys (2012). 《Boolean Function Complexity: Advances and Frontiers》. Algorithms and Combinatorics. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-642-24507-7.

[18] Alon, Noga; Vũ, Văn H (1997년 7월 1일). “Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs”. 《Journal of Combinatorial Theory, Series A》 79 (1): 133–160. doi:10.1006/jcta.1997.2780. ISSN 0097-3165.

[:0-19] 1 2 Šíma, Jiří; Orponen, Pekka (2003년 12월 1일). “General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results” (영어). 《Neural Computation》 15 (12): 2727–2778. doi:10.1162/089976603322518731. ISSN 0899-7667. PMID 14629867.

[20] Maass, W.; Schnitger, G.; Sontag, E.D. (1991). 〈On the computational power of sigmoid versus Boolean threshold circuits〉. 《[1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science》. IEEE Comput. Soc. Press. 767–776쪽. doi:10.1109/SFCS.1991.185447. ISBN 978-0-8186-2445-2.

[:2-21] 1 2 3 4 5 6 7 Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György (4월 1993). “Threshold circuits of bounded depth” (영어). 《Journal of Computer and System Sciences》 46 (2): 129–154. doi:10.1016/0022-0000(93)90001-D.

[:3-22] 1 2 Parberry, Ian; Schnitger, Georg (1989년 1월 1일). “Relating Boltzmann machines to conventional models of computation”. 《Neural Networks》 2 (1): 59–67. doi:10.1016/0893-6080(89)90015-4. ISSN 0893-6080.

[23] Ajtai, Miklos; Ben-Or, Michael (1984). 〈A theorem on probabilistic constant depth Computations〉 (영어). 《Proceedings of the sixteenth annual ACM symposium on Theory of computing - STOC '84》. ACM Press. 471–474쪽. doi:10.1145/800057.808715. ISBN 978-0-89791-133-7.

[24] Forster, Jürgen; Krause, Matthias; Lokam, Satyanarayana V.; Mubarakzjanov, Rustam; Schmitt, Niels; Simon, Hans Ulrich (2001), 〈Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity〉, Hariharan, Ramesh; Vinay, V.; Mukund, Madhavan (편집), 《FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science》 2245, Berlin, Heidelberg: Springer Berlin Heidelberg, 171–182쪽, doi:10.1007/3-540-45294-x_15, ISBN 978-3-540-43002-5, 2025년 3월 19일에 확인함

[25] Håstad, Johan; Goldmann, Mikael (6월 1991). “On the power of small-depth threshold circuits” (영어). 《Computational Complexity》 1 (2): 113–129. doi:10.1007/BF01272517. ISSN 1016-3328.

[26] Allender, E. (10월 1989). 〈A note on the power of threshold circuits〉. 《30th Annual Symposium on Foundations of Computer Science》. 580–584쪽. doi:10.1109/SFCS.1989.63538. ISBN 0-8186-1982-1.

[27] Yao, Andrew Chi-Chih (1990). 〈On ACC and threshold circuits〉. 《31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22–24, 1990, Volume II》. IEEE Computer Society. 619–627쪽. doi:10.1109/FSCS.1990.89583. ISBN 0-8186-2082-X.

[28] Sherstov, Alexander A. (2009), “Separating $AC 0$ from depth-2 majority circuits”, 《SIAM Journal on Computing》 38 (6): 2113–2129, doi:10.1137/08071421X, MR 2491551

v t e 복잡도 종류
효율적 해결 가능	DLOGTIME AC⁰ ACC⁰ REG TC TC⁰ L SL RL FL NL NL-완전 NC SC CC P P-완전 ZPP RP BPP BQP APX FP
비효율적 추정	UP NP NP-완전 NP-난해 Co-NP Co-NP-완전 TFNP FNP AM QMA PH ⊕P PP #P #P-완전 IP PSPACE PSPACE-완전
효율적 해결 불가능	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY NONELEMENTARY PR R RE ALL
기타 복잡도 종류	polyL QP
종류별 위계	다항 위계 지수 위계 그르제고르치크 위계 산술적 위계 불리언 위계
복잡도 계열	DTIME NTIME DSPACE NSPACE PCP 대화형 증명 시스템
복잡도 종류 목록

TC0

정의