회로 복잡성

이론 컴퓨터 과학에서 회로 복잡성은 부울 함수를 계산하는 부울 회로의 크기나 깊이에 따라 분류되는 계산 복잡성 이론의 한 분야다.관련 개념은 회로 $C{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,$$…의 균일한 계열의 회로 $C_{1}, C_{2},\ldots }$에 의해 결정되는 재귀 언어의 회로 복잡성이다($$아래 참조).null

부울 회로의 크기에 대한 하한을 입증하는 것은 명시적 부울 함수를 계산하는 것이 복잡성 클래스를 분리하는 일반적인 접근법이다.예를 들어, 눈에 띄는 회로 등급 P/폴리에는 다항식 크기의 회로에 의해 계산할 수 있는 부울 함수로 구성된다.$N{\displaystyle \mathsf{}}$ ${\displaystyle \mathsf{P}}$ ${\displaystyle ⊈}$ ${\displaystyle P\mathsf{}\mathsf{}}$/ ${\displaystyle p\mathsf{}}$ ${\displaystyle \mathsf{o}}$ l ${\$이(가) P와 NP를 분리한다는$$ 것을 증명한다(아래 참조).null

부울 회로의 관점에서 정의된 복잡도 등급에는⁰ AC, AC, TC⁰, NC¹, NC, P/폴리 등이 있다.null

크기 및 깊이

$n{\displaystyle }$ ${\displaystyle n}$ 입력$$ 비트를 가진 부울 회로는 모든 노드(대개 이 맥락에서 게이트라고 함)가 n ${\displaystyn}$ 입력$$ 비트 중 하나에 의해 라벨링된 인도 0의 입력 노드, AND 게이트, OR 게이트 또는 NOT 게이트인 방향의 AC 반복 그래프입니다.이러한 관문 중 하나가 출력 관문으로 지정되어 있다.그러한 회로는 $자연적$으로 n ${\displaystyle n$} 입력의$$ 함수를 계산한다.회로의 크기는 회로가 포함하는 관문의 수이며 깊이는 입력 게이트에서 출력 게이트까지의 경로의 최대 길이이다.null

회로 복잡성에^[1] 대한 두 가지 주요한 개념이 있다. 부울 함수 $f{\displaystyle }$ ${\displaystyle f}$의 회로 크기 복잡성은 $모든$ 회로 계산 f ${\displaystyle f}$의 최소 크기다$.$부울 함수 $f{\displaystyle }$ ${\displaystyle f}$의 회로 깊이 복잡성은 모든$$ 회로 계산 $f{\displaystyle }$ ${\displaystyle f}$의 최소 깊이 입니다$.$

이러한 개념은 비트 길이가 다른 문자열, 특히 무한정 형식 언어를 포함하는 모든 언어의 회로 복잡성을 고려할 때 일반화된다.그러나 부울 회로는 고정된 수의 입력 비트만 허용한다.따라서, 어떤 부울 회로도 그러한 언어를 결정할 수 없다.$이러한{\displaystyle {}_{}}$ 가능성을 설명하기 위해, $각{\displaystyle {}_{}}$ ${\displaystyle {Cn}_{}}$${\$$displaystyle$ $C_{1}, C_{2},\ldots }$의 회로 패밀리를 고려한다. 여기서$$ 각 Cn ${\displaystyle C_$${$$n$$}$은(는) n $크기$의 입력을 수용한다$.$ 각 회로 패밀리는 회로 ${\displaystyle C_{}}$ $n{\displaystyle {}_{}}$ ${\$$ng{\displaystyle }$ $길이{\displaystyle \mathrm{}}$ n$${\$displaystyle$n} 문자열이$$ 패밀리의 멤버인$$ 경우 ng 1 {\displaystyle $1}$ 및 $그렇지{\displaystyle \mathrm{}}$ 않은 경우$$ 0 ${\displaystyle 0}.$${\displaystyle {Cn}_{}}$ ${\$보다 작은 회로$($$$심층 최소 패밀리의 경우)로 어떤 크기의 입력도 결정하는 다른 패밀리가 없다면 회로 패밀리는 최소 크기라고 우리는 말한다$.$그러므로 회로 복잡성은 비재귀 언어에도 의미가 있다.균일한 패밀리의 개념은 회로 복잡성의 변형이 재귀 언어의 알고리즘 기반 복잡성 측정과 관련되도록 한다.그러나 균일하지 않은 변형은 주어진 언어를 결정하기 위해 회로 계열이 얼마나 복잡해야 하는지에 대한 하한을 찾는 데 도움이 된다.null

따라서 형식 언어 $A{\displaystyle }${\$displaystyle A}$의 회로 크기 복잡성은 최소 회로 $C{\displaystyle {}_{}}$ {${\displaystyle n_{}}$ ${\$$displaystyle t:\mathb {N}$에 대한 입력 길이 $n{\displaystyle }${\$displaystyle n$과$($와) 관련된 $함수{\displaystyle }$t :${\displaystyle N\mathbb{}}$ → ${\displaystyle N\mathbb{}}${\$displaystyle C_{n}}$로 정의된다$$.s 해당 길이의 입력이 $A{\displaystyle }$ ${\displaystyle A}$에 있는지 여부$.$회로 깊이 복잡성은 유사하게 정의된다.null

균일성

부울 회로는 가능한 모든 입력 길이에 동일한 계산 장치를 사용하는 튜링 기계와 같은 균일한 모델과 대조적으로 서로 다른 길이의 입력이 다른 회로에 의해 처리된다는 점에서 소위 불균일 연산 모델의 대표적인 예 중 하나이다.따라서 개별 계산 문제는 특정 부울 회로 $계열$의 C ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{C\mathrm{}}_{}}$ ${\displaystyle {}_{}}$… ${\displaystyle C_{1}, C_{2},\dots }$과(와) 연관된다. 여기서$$ 각 $C{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$은 n비트의 회로 처리 입력이다$$.균일성 조건은 입력 n에서 개별 회로 C n ${\$에 대한 설명을 생성하는 자원이 있는 튜링 기계의 존재를 요구하는 경우가 많다$.$ 이 튜링 기계의 작동 시간 다항식이 n에 있을 때 회로 계열은 P-uniform이라고 한다.DLOGTIME-균일성의 보다 엄격한 요건은 특히 AC⁰ 또는⁰ TC와 같은 얕은 깊이의 회로 등급 연구에 관심이 있다.리소스 한계가 지정되지 않은 경우, 언어가 동일한 부울 회로 계열에 의해 결정되는 경우에만 언어가 재귀적(즉, 튜링 기계에 의해 해독 가능)이다.null

다항식 시간 균일

\${N}${N} $displaystyle \{C_{n}:n\in \mathb$ {N} $\}}$의 부울 회로 제품군은 다음과 같은 결정론적 튜링 시스템 M이 있는 경우 다항식 시간 균일하다.

• M은 다항식 시간으로 실행됨
• 모든 $n{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle N\mathbb{}}$ ${\$에 대해$,$ M은 입력 ${\displaystyle {1n}^{}}$ ${\$에 ${\displaystyle {대한}_{}}$ 설명을 출력한다.

로그스페이스 유니폼

\$mathb{N} \mathb$ {$N}$의 부울 회로 제품군은 다음과 같은 결정론적 튜링 시스템 M이 있는 경우 로그 공간 균일하다.

• M은 로그 공간에서 실행됨
• 모든 $n{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle N\mathbb{}}$ ${\$에 대해$,$ M은 입력 ${\displaystyle {1n}^{}}$ ${\$에 ${\displaystyle {대한}_{}}$ 설명을 출력한다.

역사

회로 복잡성은 1949년 섀넌으로 거슬러 올라간다.^[2] 섀넌은 n 변수의 거의 모든 부울 함수에 크기 θ(2ⁿ/n)의 회로가 필요하다는 것을 증명했다.이러한 사실에도 불구하고, 복잡성 이론가들은 계산하기 어려운 목적으로 명시적으로 구성된 함수에 대한 초항식 회로 하한을 증명할 수 있을 뿐이었다.null

더 일반적으로, 초다항식 하한은 사용된 회로 계열에 대한 특정 제한 하에서 증명되었다.초폴리놈 회로 하한을 처음으로 보여준 기능은 입력 비트 모듈로 2의 합계를 계산하는 패리티 함수였다.패리티가 AC에⁰ 포함되지 않는다는 사실은 1983년^[3][4] 아제타이에 의해 독립적으로, 1984년 퍼스트, 작센, 시퍼에 의해 처음 확립되었다.^[5]이후 1987년^[6] Håstad에 의한 개선은 패리티 함수를 계산하는 일정한 깊이 회로의 모든 제품군에 지수적 크기가 필요하다는 것을 확립했다.1987년^[8] 스몰렌스키(Smolensky)는 라즈보로프의 결과를 확장하면서 입력 비트의 합계를 계산하는 게이트로 회로가 증강되어도 이상 prime p라는 것을 증명했다.^[7]

k-clike 문제는 n 꼭지점에 있는 특정 그래프의 크기가 k인지 여부를 결정하는 것이다.상수 n과 k를 특별히 선택하는 경우, 그래프는${\displaystyle }$(${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{n}}{}}$ 2${\displaystyle }$) ${\$ 2$.}비트$를 사용하여 이진수로 인코딩할 수 있으며, 이 비트는 가능한$$ 각 에지에 대해 존재 여부를 표시한다.그런 다음 k-clik 문제는 $함수{\displaystyle {}_{}}$ f ${\displaystyle \mathrm{k}{}_{}}$:${\displaystyle }${ 0${\displaystyle ,}$ ${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle {(n\genfrac{}{}{0ex}{}{2}{}}^{}}$) → { ${\displaystyle 0,}$ ${\displaystyle 1}$}$${\$displaystyle f_{k$$}:\{0$$,$$1\}^{n \}$$$$\선택$하여 ${\displaystyle {문자열}_{}}$로 인코딩된 그래프가 k 크기의 클릭을 포함하는 경우에만$$ $1$을 출력한다$$.이 기능 계열은 단조형이며 회로 계열에서 계산할 수 있지만, 다항식 크기의 단조형 회로 계열(AND 및 OR 관문이 있는 회로는 부정 없이)으로는 계산할 수 없는 것으로 나타났다.1985년^[7] 라즈보로프의 원래 결과는 이후 1987년 알론과 보파나에 의해 기하급수적인 크기의 하한선으로 개선되었다.^[9]로스만은 2008년^[10], 평균적인 케이스에서도 k-clike 문제를 해결하기$$ 위해 AND, OR, NOT 게이트로 일정한 깊이 회로가 $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle ({n\mathrm{}}^{}}$ ${\displaystyle k^{}}$/ 4$){\displaystyle \Oomega (n^{k/4})$의 크기가 필요하다는 것을 보여주었다.더욱이, ${\displaystyle {크기}_{}}$ $n{\displaystyle {}^{}}$ ${\displaystyle k^{}}$/ ${\displaystyle 4^{}}$+ O${\displaystyle {}^{}}$( 1$$){\$displaystyle n^{k/4+O(1)}$의 회로가 있어서$$ f k ${\$를 계산한다$.$

1999년 라즈와 맥켄지는 이후 단조로운 NC 서열이 무한하다는 것을 보여주었다.^[11]null

정수 분할 문제는 균일한 TC에⁰ 있다.^[12]null

회로 하한

회로 하한은 일반적으로 어렵다.알려진 결과는 다음과 같다.

• 패리티는 1983년^[3][4] 아제타이는 물론 1984년 퍼스트, 작센, 시퍼에 의해 증명된 통일 AC에⁰ 있지 않다.^[5]
• 앨렌더가 입증한 PP에는 균일한 TC가⁰ 엄격히 포함되어 있다.^[13]
• 클래스 S^P
  ₂, PP^{[nb 1]} 및 MA/1^[14](하나의 조언이 있는 MA)은 상수 k에 대해 SIZE(n^k)가 아니다.
• 균일하지 않은⁰ 등급 ACC에 다수 함수가 포함되어 있지 않은 것으로 의심되지만, 윌리엄스는 $2010년$에야 N E ${\displaystyle \mathsf{X}}$ ${\displaystyle \mathsf{P}{0}^{\mathrm{}}}$ A ${\displaystyle {\mathsf{C}}^{}}$0{\$displaystyle${\$mathsf{$NEXP$}}}\not$ \subseteq {\$mathsf {AC}^{0$^[15]을 증명했다.

NEXPTIME이 균일하지 않은 TC회로를⁰ 가지고 있는지 여부는 개방되어 있다.null

회로 하한에 대한 증명은 디랜도밍과 강하게 연관되어 있다.A proof that ${\displaystyle {\mathsf {P}}={\mathsf {BPP}}}$ would imply that either ${\displaystyle {\mathsf {NEXP}}\not \subseteq {\mathsf {P/poly}}}$ or that permanent cannot be computed by nonuniform arithmetic circuits (polynomials) of polynomial size and polynomial degree.^[16]null

1997년에, 라즈보로프와 루디치는 명시적 부울 함수에 대해 알려진 많은 회로 하한선이 각각의 회로 등급에 대해 유용한 소위 자연적 특성의 존재를 암시한다는 것을 보여주었다.^[17]반면에 P/폴리에게 유용한 자연적 특성은 강한 유사성 생성기를 파괴할 것이다.이는 강한 회로 하한을 증명하기 위한 "자연적인 증거" 장벽으로 해석되는 경우가 많다.2016년 카르모시노, 임파글리아초, 카바네츠, 코로콜로바 등은 자연성이 효율적인 학습 알고리즘 구축에도 활용될 수 있다는 것을 입증했다.^[18]null

복잡도 클래스

많은 회로 복잡성 클래스는 클래스 계층 구조로 정의된다.음이 아닌 각 정수 i에 대해, 경계 팬인 AND, OR 및 NOT 게이트를 사용하는$$$깊이{\displaystyle }$ O${\displaystyle ({\log }^{}}$ ${\displaystyle i^{}}$ ${\displaystyle {}^{}}$(${\displaystyle n}$)${\displaystyle$ O$(\log ^{i}(n)})$의 다항식 크기 회로로 구성된 클래스 NC가ⁱ 있다.이 모든 계층의 조합 NC가 논의 대상이다.언바운드 팬인 게이트를 고려하여 ACⁱ 및 AC 등급(NC와 동일)을 구성할 수 있다.동일한 크기와 깊이 제한을 가진 많은 다른 회로 복잡성 등급은 다른 관문 세트를 허용하여 구성할 수 있다.null

시간 복잡성과의 관계

특정 $언어$인 ${\displaystyle A}$이$($가) 시간 복합 클래스 ${\displaystyle \text{TIME}(t}$ ${\displaystyle (n}$ ${\displaystyle )}$ ${\displaystyle {\text{$$TIME}}(t(n))}$ for some function ${\displaystyle t:\mathbb {N} \to \mathbb {N} }$, then ${\displaystyle A}$ has circuit complexity ${\displaystyle {\mathcal {O}}(t(n)\log t(n))}$. If the Turing Machine that accepts the language is oblivious (meaning that it reads and writes the same입력에 관계없이 메모리 셀) 그러면 $A{\displaystyle }$ ${\displaystyle$ A$}$은(는) 회로 $복잡도{\displaystyle \mathcal{}}$ O${\displaystyle }$( (${\displaystyle t}$)${\displaystyle {\mathcal {O}(t(n)})}$을(를) 갖는다$.$^[19]

참고 항목

• 회로 최소화

메모들

참조

추가 읽기

• Vollmer, Heribert (1999). Introduction to Circuit Complexity: a Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer Verlag. ISBN 978-3-540-64310-4.
• 베게너는 인고(1987년)[1986년 11월].부울 함수의 복잡성.Wiley–Teubner 시리즈 컴퓨터 사이언시스에.프랑크푸르트 Main/Bielefeld, 독일:JohnWiley도&Sons회사와 BG.Teubner 출판사., 슈투트가르트.아이 에스비엔 3-519-02107-2.LCCN 87-10388.(xii+457 페이지)(주의..그때 이 문제에 대한 영향력 있는 교과서 일반적으로"불루 북"으로 알려져 있다.계산 복잡성에 대한 전자 콜로키움에서 다운로드(PDF) 가능)
• Zwick, Uri. "Lecture notes for a course of Uri Zwick on circuit complexity".