NC (복잡도)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

NC는 다항식 개수의 프로세서를 가진 병렬 컴퓨터에서 다항 로그 시간 안에 해결 가능한 판정 문제의 집합으로 정의된다. NC에는 정수 연산, 행렬 연산, 최대 매칭 찾기 등 다양한 문제가 포함된다. NC는 NC¹ ⊆ NC² ⊆ … ⊆ NC의 관계를 갖는 NC 계층으로 구성되며, L, NL, AC, P 등 다른 복잡도 클래스와 관계를 가진다. NC⁰는 입력 비트의 상수 길이에 대해서만 작동하는 함수들의 클래스이다. 배링턴 정리는 경계 너비 분기 프로그램과 비균일 NC¹이 같음을 나타낸다.

NC (복잡도)

📚 더 읽어볼만한 페이지

회로 복잡도 - 스위칭 회로 이론
회로 복잡도 - 다수결 함수
다수결 함수는 부울 회로에서 입력의 과반수가 참일 때 참을 반환하는 논리 게이트로, 전가산기의 자리올림수 출력이나 오류 수정 등에 활용되며, 짝수 입력 시 동점 처리 방식이 필요하고 다항식 크기의 명시적 공식을 구하는 다양한 방법이 있다.
복잡도 종류 - P (복잡도)
P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다.
복잡도 종류 - P-NP 문제
P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.

1. 개요
2. NC의 정의와 문제
3. NC 계층
4. NC⁰
5. 배링턴 정리 (Barrington's Theorem)

2. NC의 정의와 문제

NC에는 다음을 포함한 많은 문제가 있는 것으로 알려져 있다.

* 정수 덧셈, 곱셈 및 나눗셈
* 행렬 곱셈, 행렬식, 역행렬, 계수
* 실베스터 행렬을 사용한 선형 대수로의 환원을 통한 다항식 최대공약수
* 최대 매칭 찾기

이러한 문제에 대한 알고리즘은 가우스 소거법과 유클리드 알고리즘과 같이 순차적으로 수행되는 연산에 의존하는 잘 알려진 알고리즘과는 달리, 별도로 발명해야 하는 경우가 많았다. 리플 캐리 덧셈기와 자리수 예측 가산기는 병렬 알고리즘의 예시이다.

NC¹ 문제의 한 예로, 1과 0으로 구성된 문자열에서 1의 개수를 세는 비트열 패리티 검사가 있다. 이 문제는 문자열의 모든 비트를 더하여 해결할 수 있다. 덧셈은 결합 법칙이 성립하므로, 다음과 같은 식이 성립한다.

: $x_1 + \cdots + x_n = \left(x_1 + \cdots + x_{\frac{n}{2}}\right) + \left(x_{\frac{n}{2} + 1} + \cdots + x_n\right)$ .

이러한 속성을 재귀적으로 적용하면, 두 비트 $x_i$ 와 $x_j$ 사이의 모든 합이 기본 논리 연산자를 통해 표현될 수 있는 길이 $O(\log(n))$ 의 이진 트리를 구성할 수 있다. 예를 들어, 부울 표현식 $(x_i \land \neg x_j) \lor (\neg x_i \land x_j)$ 를 통해 표현할 수 있다.

3. NC 계층

NCⁱ는 최대 두 개의 입력을 갖는 다항 개수의 게이트와 깊이 O((log n)ⁱ)인 균일한 부울 회로로 결정 가능한 결정 문제의 집합이거나, 다항 개수의 프로세서를 갖는 병렬 컴퓨터에서 O((log n)ⁱ) 시간 안에 해결 가능한 결정 문제의 집합이다. 다음이 성립한다.

: $\mathsf{NC}^1 \subseteq \mathsf{NC}^2 \subseteq \cdots \subseteq \mathsf{NC}^i \subseteq \cdots \mathsf{NC}$

이는 NC-계층을 형성한다.

NC 클래스는 공간 클래스 L 및 NL, AC와 관련이 있다.

: $\mathsf{NC}^1 \subseteq \mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{AC}^1 \subseteq \mathsf{NC}^2 \subseteq \mathsf{P}.$

NC 클래스는 AC 클래스와 유사하게 정의되지만, AC 클래스는 무제한 팬인을 가진 게이트를 사용한다. 각 i에 대해 다음이 성립한다.

: $\mathsf{NC}^i \subseteq \mathsf{AC}^i \subseteq \mathsf{NC}^{i+1}.$

이로부터 NC = AC임을 알 수 있다. i = 0일 때 위의 두 포함 관계는 모두 엄격하다.

NC는 각 단계에서 최대 두 개의 선택지를 가지며 O(log n) 공간과 $(\log n)^{O(1)}$ 교대를 갖는 교대 튜링 기계에서 해결 가능한 문제와 동등하다.

계산 복잡도 이론에서 중요한 미해결 문제는 NC 계층 내의 모든 포함 관계가 엄격한지 여부이다. 파파디미트리우(Papadimitriou)는 어떤 i에 대해 NCⁱ = NCⁱ⁺¹이 성립하면 모든 j ≥ i에 대해 NCⁱ = NC^j가 성립하며, 결과적으로 NCⁱ = NC가 된다는 것을 보였다. 이 관찰은 NC-계층 축소라고 불리는데, 이는 포함 관계의 사슬

: $\mathsf{NC}^1 \subseteq \mathsf{NC}^2 \subseteq \cdots$

에서 단 하나의 등식만 성립해도 전체 NC 계층이 어떤 수준 i로 "축소"되기 때문이다. 따라서 다음 두 가지 가능성이 존재한다.

# $\mathsf{NC}^1 \subset \cdots \subset \mathsf{NC}^i \subset \cdots \subset \mathsf{NC}^{i+j} \subset \cdots \mathsf{NC}$
# $\mathsf{NC}^1 \subset \cdots \subset \mathsf{NC}^i = \cdots = \mathsf{NC}^{i+j} = \cdots \mathsf{NC}$

대부분 (1)이 사실이라고 믿지만, 두 명제 중 어느 것이 참인지에 대한 증명은 아직 발견되지 않았다.

4. NC<sup>0</sup>

NC⁰는 입력 비트의 상수 길이에 대해서만 작동하는 함수들의 집합이다. 상수 깊이와 경계된 팬인(fan-in)을 가진 균일한 부울 회로로 정의할 수 있다.

5. 배링턴 정리 (Barrington's Theorem)

BWBP는 경계 너비와 다항식 길이의 분기 프로그램 패밀리에 의해 인식 가능한 언어 클래스를 나타낸다.

배링턴의 정리에 따르면, BWBP는 정확히 비균일 NC¹이다. 이 증명은 대칭군 S₅의 비가해성을 사용한다.

이 정리는 매우 놀랍다. 예를 들어, 이는 다수결 함수가 상수 너비와 다항식 크기의 분기 프로그램 패밀리에 의해 계산될 수 있음을 의미하지만, 직관적으로 다항식 크기를 달성하려면 선형 수의 상태가 필요할 수 있다.

상수 너비와 다항식 크기의 분기 프로그램은 쉽게 (분할 정복을 통해) NC¹ 회로로 변환될 수 있다.

반대로, NC¹ 회로가 주어졌다고 가정할 때, AND 및 NOT 게이트만 사용한다고 가정해도 일반성을 잃지 않는다.

분기 프로그램이 회로 C의 출력이 0일 때는 항등 함수로 작동하고, 출력이 1일 때는 α로 작동하는 경우, 해당 분기 프로그램이 C를 α-계산한다고 부른다.

정리 1과 길이 5의 모든 사이클이 공액이라는 사실의 결과로, 두 개의 5-사이클 α, β에 대해, 분기 프로그램이 회로 C를 α-계산하는 경우, 동일한 길이의 회로 C를 β-계산하는 분기 프로그램이 존재한다.

분기 프로그램의 크기는 최대 4^d이며, 여기서 d는 회로의 깊이이다. 회로가 로그 깊이를 갖는 경우, 분기 프로그램은 다항식 길이를 갖는다.