회로(컴퓨터 과학)

이론 컴퓨터 과학에서 회로는 입력 값이 함수를 계산하는 게이트의 시퀀스를 통과하는 계산 모델입니다.이러한 종류의 회로는 부울 회로의 일반화와 디지털 논리 회로의 수학적 모델을 제공합니다.회로는 회로에 포함된 게이트와 게이트가 생성할 수 있는 값에 의해 정의됩니다.예를 들어 부울 회선의 값은 부울 값이며 회로에는 접속 게이트, 절단 게이트 및 부정 게이트가 포함됩니다.정수회로의 값은 정수 집합과 게이트 집합의 합집합, 집합 교집합 및 집합 보집 집합과 산술 연산의 덧셈 및 곱셈입니다.

형식적 정의

회로는 트리플$({\displaystyle M,}$ $)\displaystyle$$M, L, G)$입니다.

• $(\displaystyle$ M$)$은 일련의 값입니다.
• ${\displaystyle L}${\$displaystyle$ L$}$은 게이트 라벨 세트이며, 각 라벨은 음이 아닌 $정수{\displaystyle }$i$${\$displaystyle$ i$}$에서 ${\displaystyle M^{}}$$${\$displaystyle$ M$}$까지의 함수입니다($여기$서$$i {\$displaystyle$ i$}$는 게이트에 대한 입력 수를 나타냅니다$$).
• ${\displaystyle G}${\$displaystyle$ G$}$는$$L {\$displaystyle$ L$\}$의 라벨이 붙은 방향 비순환 그래프입니다.

그래프의 꼭지점을 게이트라고 합니다.$In-displaystyle$$$i의 각 $게이트{\displaystyle }$g$({$$displaystyle$ g$})$에 대해 $.({displaystyle$ M^{i})에 $"{displaystyle\ell}"$이 정의되어 있는 경우에만 $게이트{\displaystyle }$g(\$displaystyle$ g$)$에$$L(\$displaystyle$ L$)$의 $요소{\displaystyle }$ $"{displaystyle$\ell$}"$로 라벨을 붙일 수 있습니다.$}$

용어.

도수가 0인 게이트를 입력 또는 리브라고 합니다.out-degree 0의 게이트는 출력이라고 불립니다.$G$에 $G$에서 $H$까지 가장자리가 있는 경우$(\$$displaystyle$$$G$)$$h$는 g의 $자식{\displaystyle }$(\$displaystyle$$$g$)$이라고 합니다.그래프의 정점에 순서가 있다고 가정하면 게이트의$$k번째 자식(\$displaystyle$ k$)$을 $말할{\displaystyle }$ 수 있습니다.$n{\displaystyle }$ k$(\displaystyle$ k$)$가 게이트의 아웃도보다 작습니다.

회선의 크기는 회선의 노드 수입니다.$g$의 깊이($displaystyle$ g$)$는$g$에서 $시작$하여$출력$ 게이트까지 G에서 가장 긴 경로의 길이입니다.특히 깊이 1의 게이트는 out-degree 0이 유일하다.회로의 깊이는 게이트의 최대 깊이입니다.

$레벨{\displaystyle }$ i$(displaystyle$ i$)$는 깊이 $(displaystyle$i$)$의 모든 게이트 집합입니다. 레벨 제어 회로는 $깊이{\displaystyle }$ i$(displaystyle$ i$)$의 게이트에 대한 가장자리가 $깊이{\displaystyle }$ i$(displaystyle i+1$) 또는$$ 입력에서 나오는 회로입니다.즉, 에지는 회로의 인접 레벨 사이에만 존재합니다.레벨링 회로의 폭은 모든 레벨의 최대 크기입니다.

평가하기

$in-displaystyle i$및$$ l$라벨$이 {\$displaystyle$ l$$$}$인 $게이트$g {\$displaystyle$v$(g)}$의 정확한 $값{\displaystyle }$ V$)$는 모든 $게이트{\displaystyle }$g {\$displaystyle$g$\}$에 대해 재귀적으로 정의됩니다.

${\displaystyle V(g)=begin{case}l&{\text{if}}}g(텍스트{는 입력}}\l(V(g_{1}),\dotsc,V(g_{i})})&{\text{case,}}\end{case}}$

$여기$서 각 $(\$j$$})는$$g(\$displaystyle$ g$)$의 부모입니다.

회로의 값은 각 출력 게이트의 값입니다.

기능으로서의 회로

잎의 라벨은 M$(\displaystyle$$$M$)$의 값을 취하는 변수도 될 수 있습니다.n$(\$$displaystyle$ M$^{n})$의 경우 ${\displaystyle {회선}^{}}$은 M$(\$displaystyle M^{n})에서$$M(\$displaystyle$ M$)$까지의 함수로 볼 수 있습니다.$이$ 경우 일반적으로 회로${\displaystyle }$패밀리(${\displaystyle {Cn}_{}{)}_{}}$를 고려합니다$.$$playstyle (C_{n})_{n\in \mathbb {N$ $회선{\displaystyle {}_{}}$ $(\$$displaystyle$ $C_{n$$})$에$$n개의 $변수$가 $있는{\displaystyle }$ 정수로 인덱스된 일련의 회선.회선 패밀리는 M ${\$ { \ $displaystyle$ M $^$ { * } $m$ m M$$（ \ $display style$ M$）$ 까지의 함수로 볼 수 있습니다.

크기, 깊이 및 폭에 대한 개념은 N$(\$에서 N$(\$까지 자연스럽게 확장될 수 있습니다. 예를 들어, ${\displaystyle \mathrm{si}}$z ${\displaystyle e(}$n$)$ {$displaystyle size($n$$)}는 제품군의 n$(\displaystyle$ n$)$ 회로${\displaystyle }$ 크기입니다.

복잡성과 알고리즘 문제

특정 입력에 대한 특정 부울 회로의 출력을 계산하는 것은 P-완전 문제입니다.단, 입력이 정수회선일 경우 이 문제가 결정 가능한지는 알 수 없습니다.

회로 복잡도는 부울 함수를 계산할 수 있는 회로의 크기 또는 깊이에 따라 분류하려고 합니다.

「 」를 참조해 주세요.

• 산술 회로의 복잡도
• 부울 회로
• 회로의 복잡성
• 자연수 집합 이상의 회로
• 복잡도 등급 NC, AC 및 TC
• 양자 회로 및 BQP

레퍼런스

• Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 978-3-540-64310-4.
• Yang, Ke (2001). "Integer Circuit Evaluation Is PSPACE-Complete". Journal of Computer and System Sciences. 63 (2, September 2001): 288–303. doi:10.1006/jcss.2001.1768. ISSN 0022-0000.