회로 (컴퓨터 과학)

이론 컴퓨터 과학에서 회로(circuit)는 입력값이 일련의 게이트를 거치며 진행되고, 각 게이트가 함수를 계산하는 계산 모델이다. 이러한 종류의 회로는 불 회로의 일반화를 제공하며 디지털 논리 회로를 위한 수학적 모델이 된다. 회로는 회로가 포함하는 게이트와 게이트가 생성할 수 있는 값에 의해 정의된다. 예를 들어, 불 회로의 값은 불 값이며, 회로는 논리곱, 논리합, 부정 게이트를 포함한다. 정수 회로의 값은 정수의 집합이며 게이트는 집합의 합집합, 교집합, 여집합뿐만 아니라 덧셈과 곱셈 같은 산술 연산을 계산한다.

형식적 정의

회로는 $(M,L,G)$ 라는 세 요소의 튜플이다. 여기서

$M$ 은 값의 집합이다.
$L$ 은 게이트 레이블의 집합으로, 각 레이블은 어떤 비음의 정수 $i$ 에 대하여 $M^{i}$ 에서 $M$ 으로 가는 함수이다 (여기서 $i$ 는 게이트로 들어가는 입력의 개수를 나타낸다).
$G$ 는 $L$ 의 레이블을 가진 유향 비순환 그래프이다.

그래프의 정점은 게이트라고 불린다. 진입 차수가 $i$ 인 각 게이트 $g$ 에 대하여, 게이트 $g$ 는 $\ell$ 이 $M^{i}$ 에서 정의될 때에만 $L$ 의 원소 $\ell$ 로 레이블링될 수 있다.

용어

진입 차수가 0인 게이트는 입력 또는 리프(leaf)라고 불린다. 진출 차수가 0인 게이트는 출력이라고 불린다. 만약 그래프 $G$ 에서 게이트 $g$ 에서 게이트 $h$ 로 가는 간선이 있다면, $h$ 를 $g$ 의 자식이라고 부른다. 그래프의 정점들 사이에 순서가 있다고 가정하므로, $k$ 가 게이트의 진출 차수보다 작거나 같을 때 게이트의 $k$ 번째 자식에 대해 말할 수 있다.

회로의 크기는 회로 노드의 개수이다. 게이트 $g$ 의 깊이는 $g$ 에서 시작하여 출력 게이트까지 이어지는 최장 경로의 길이이다. 특히 진출 차수가 0인 게이트만이 깊이가 1인 게이트이다. 회로의 깊이는 모든 게이트의 깊이 중 최댓값이다.

레벨 $i$ 는 깊이가 $i$ 인 모든 게이트의 집합이다. 레벨화된 회로(levelled circuit)는 깊이 $i$ 인 게이트로 향하는 간선이 깊이 $i+1$ 인 게이트나 입력에서만 오는 회로를 말한다. 즉, 간선은 회로의 인접한 레벨 사이에서만 존재한다. 레벨화된 회로의 너비는 임의의 레벨의 최대 크기이다.

평가

진입 차수가 $i$ 이고 레이블이 $l$ 인 게이트 $g$ 의 정확한 값 $V(g)$ 는 모든 게이트 $g$ 에 대해 재귀적으로 정의된다.

V(g)={\begin{cases}l&{\text{if }}g{\text{ is an input}}\\l(V(g_{1}),\dotsc ,V(g_{i}))&{\text{otherwise,}}\end{cases}}

여기서 각 $g_{j}$ 는 $g$ 의 부모이다.

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

함수로서의 회로

리프의 레이블은 $M$ 의 값을 가지는 변수가 될 수도 있다. 만약 $n$ 개의 리프가 있다면, 회로는 $M^{n}$ 에서 $M$ 으로 가는 함수로 볼 수 있다. 이때 정수로 인덱싱된 회로의 열인 회로 가족 $(C_{n})_{n\in \mathbb {N} }$ 을 고려하는 것이 일반적이며, 여기서 회로 $C_{n}$ 은 $n$ 개의 변수를 갖는다. 따라서 회로 가족은 $M^{*}$ 에서 $M$ 으로 가는 함수로 볼 수 있다.

크기, 깊이, 너비의 개념은 함수 가족으로 자연스럽게 확장되어 $\mathbb {N}$ 에서 $\mathbb {N}$ 으로 가는 함수가 된다. 예를 들어, $size(n)$ 은 가족 중 $n$ 번째 회로의 크기이다.

복잡도 및 알고리즘 문제

특정 입력에 대해 주어진 불 회로의 출력을 계산하는 것은 P-완전 문제이다. 그러나 입력이 정수 회로인 경우, 이 문제가 결정 가능한지는 알려져 있지 않다.

회로 복잡도는 불 함수를 계산할 수 있는 회로의 크기나 깊이에 따라 불 함수를 분류하고자 시도한다.

같이 보기

각주

^[1]
^[2]

↑ 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. 288–303쪽. doi:10.1006/jcss.2001.1768. ISSN 0022-0000.

[1] Vollmer, Heribert (1999). 《Introduction to Circuit Complexity》. Berlin: Springer. ISBN 978-3-540-64310-4.

[2] Yang, Ke (2001). 《Integer Circuit Evaluation Is PSPACE-Complete》. 《Journal of Computer and System Sciences》 63. 288–303쪽. doi:10.1006/jcss.2001.1768. ISSN 0022-0000.

[1]

[2]