회로 (컴퓨터 과학)

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

 형식적 정의 
회로는 라는 세 요소의 튜플이다. 여기서
 은 값의 집합이다.
 은 게이트 레이블의 집합으로, 각 레이블은 어떤 비음의 정수 에 대하여 에서 으로 가는 함수이다 (여기서 는 게이트로 들어가는 입력의 개수를 나타낸다).
 는 의 레이블을 가진 유향 비순환 그래프이다.

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

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

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

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

 평가 
진입 차수가 이고 레이블이 인 게이트 의 정확한 값 는 모든 게이트 에 대해 재귀적으로 정의된다.

여기서 각 는 의 부모이다.

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

 함수로서의 회로 
리프의 레이블은 의 값을 가지는 변수가 될 수도 있다. 만약 개의 리프가 있다면, 회로는 에서 으로 가는 함수로 볼 수 있다. 이때 정수로 인덱싱된 회로의 열인 회로 가족 을 고려하는 것이 일반적이며, 여기서 회로 은 개의 변수를 갖는다. 따라서 회로 가족은 에서 으로 가는 함수로 볼 수 있다.

크기, 깊이, 너비의 개념은 함수 가족으로 자연스럽게 확장되어 에서 으로 가는 함수가 된다. 예를 들어, 은 가족 중 번째 회로의 크기이다.

 복잡도 및 알고리즘 문제 

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

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

 같이 보기 
 산술 회로 복잡도
 불 회로
 회로 복잡도
 자연수 집합 상의 회로
 복잡도 종류 NC, AC, TC
 양자 회로 및 BQP

 각주 

분류:계산 이론
분류:회로 복잡도