NC (복잡도)

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

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

1. 개요

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

2. NC의 정의와 문제

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

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

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

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

:

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

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

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

'''NC''' 클래스는 공간 클래스 '''L'''^[7] 및 '''NL'''^[7], '''AC'''^[8]와 관련이 있다.

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

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

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

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

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

계산 복잡도 이론에서 중요한 미해결 문제는 '''NC''' 계층 내의 모든 포함 관계가 엄격한지 여부이다. 파파디미트리우(Papadimitriou)는 어떤 ''i''에 대해 '''NC'''^''i'' = '''NC'''^''i''+1이 성립하면 모든 ''j'' ≥ ''i''에 대해 '''NC'''^''i'' = '''NC'''^''j''가 성립하며, 결과적으로 '''NC'''^''i'' = '''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⁰

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

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

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

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

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

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

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

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

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

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

참조

_[1] 논문 Towards a complexity theory of synchronous parallel computation http://citeseerx.ist[...] 1981
_[2] 논문 A taxonomy of problems with fast parallel algorithms 1985-01-01
_[3] 논문 On simultaneous resource bounds https://www.infona.p[...] 1979
_[4] 서적 2009
_[5] 서적 2009
_[6] 웹사이트 Lecture 2: The Complexity of Some Problems https://lin-web.clar[...] Clarkson University 2000-07-18
_[7] 서적 Theorem 16.1 1994
_[8] 서적 2002
_[9] 서적 2002
_[10] 논문 Separating NC along the delta axis
_[11] 서적 2002
_[12] 논문 Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in '''NC'''¹ http://www.cs.umass.[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com