NC(복잡성)

계산 복잡성 이론에서, 클래스 NC ("Nick's Class"의 경우)는 다항식 프로세서 수가 있는 병렬 컴퓨터의 다항식 시간에 해독 가능한 의사결정 문제의 집합이다. 즉, O(n^k) 병렬 프로세서를 사용하여 시간 O(log^c n)로 해결할 수 있는 상수 c와 k가 존재한다면 NC에 문제가 있다. 스테판^[1][2] 쿡은 다항식 깊이와 다항식 크기를 가진 회로에 대해 광범위한^[3] 연구를 한 닉 피펜거의 이름을 따서 "닉의 클래스"라는 이름을 만들었다.^[4]

P급을 다루기 쉬운 문제(코밤의 논문)로 생각할 수 있듯이 NC도 병렬 컴퓨터에서 효율적으로 해결할 수 있는 문제로 생각할 수 있다.^[5] 다항식 시간 순차적 계산으로 다항식 병렬 계산을 시뮬레이션할 수 있기 때문에 NC는 P의 하위 집합이다. NC = P인지는 알 수 없지만, 대부분의 연구자들은 이것이 거짓이라고 의심하고 있는데, 이는 아마도 "일관적으로 순차적으로" 처리될 수 없고 병렬을 사용함으로써 현저하게 속도를 낼 수 없는 일부 추적 가능한 문제가 있다는 것을 의미한다. 클래스 NP 완성은 "아마도 다루기 어려운" 것으로 생각할 수 있듯이, NC 감소를 사용할 때 클래스 P-완성은 "아마도 병렬화가 불가능할 것" 또는 "아마도 본질적으로 순차적인" 것으로 생각할 수 있다.

정의에서 병렬 컴퓨터는 병렬 랜덤 액세스 머신(PRAM)으로 가정할 수 있다. 그것은 중앙 메모리 풀이 있는 병렬 컴퓨터인데, 어떤 프로세서가든 일정한 시간에 어떤 메모리의 비트에도 접근할 수 있다. NC의 정의는 둘 이상의 프로세서에 의한 단일 비트에 대한 동시 액세스를 PRAM이 처리하는 방법의 선택에 영향을 받지 않는다. CRCW, CREW 또는 ERW일 수 있다. 해당 모델에 대한 설명은 PRAM을 참조하십시오.

마찬가지로 NC는 다항성 깊이와 최대 팬인 2의 다항식 관문 수를 가진 균일한 부울 회로(입력 길이에서 계산할 수 있는 NC의 경우 로그 공간에서 n 크기의 부울 회로를 계산할 수 있다고 가정함)에 의해 결정 가능한 문제로 정의될 수 있다.

RNC는 NC를 무작위성으로 확장하는 클래스다.

NC의 문제

P와 마찬가지로 약간의 언어 남용으로 기능 문제와 검색 문제를 NC에 있는 것으로 분류할 수 있다. NC는 다음과 같은 많은 문제를 포함하는 것으로 알려져 있다.

• 정수 추가, 곱하기 및 나누기;
• 행렬 곱하기, 결정 요인, 역, 순위
• 다항식 GCD, 실베스터 행렬을 이용한 선형대수로 축소
• 최대 일치 항목을 찾는 중.

종종 그러한 문제들에 대한 알고리즘은 별도로 발명되어야 했고 잘 알려진 알고리즘으로부터 순진하게 적응될 수 없었다 – 가우스 제거와 유클리드 알고리즘은 순차적으로 수행된 연산에 의존한다. 리플 캐리어 어더더와 캐리어 룩 헤드 어더더를 대조할 수 있다.

예

NC의¹ 문제 예로는 비트 스트링의 패리티 체크를 들 수 있다.^[6] 문제는 1과 0으로 만들어진 문자열의 1초 수를 세는 데 있다. 간단한 해결책은 모든 문자열의 비트를 합하는 것이다. Since addition is associative, ${\displaystyle x_{1}+\cdots +x_{n}=(x_{1}+\cdots +x_{n/2})+(x_{n/2}+1+\cdots +x_{n})}$. Recursively applying such property, it is possible to build a binary tree of length ${\displaystyle O(log($$n))}$ in which every sum between two bits ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}}$ is expressible by means of basic logical operators, e.g. through the boolean expression ${\displaystyle (x_{i}\land \neg x_{j})\lor (\neg x_{i}\land x_{j})}$.

NC 계층

NC는ⁱ 다항식 입력과 깊이 O(logⁱ n)의 다항식 게이트 수를 가진 균일한 부울 회로에 의해 해독 가능한 의사결정 문제의 등급이거나, 다항식 프로세서가 있는 병렬 컴퓨터의 시간 O(logⁱ n)에서 해결 가능한 의사결정 문제의 등급이다. 분명히, 우리는

${\displaystyle {\mathsf {NC}^{1}\subseteq {\mathsf {NC}}\subseteq \subseteq \subseteq {nc}^{i}}\subseteq \mathsf {NC}}}}}}}}}}$

NC-히어러시즘을 형성하고 있어

우리는 NC 클래스를 L, NL^[7], AC 스페이스 클래스와 연관시킬 수 있다.^[8]

${\displaystyle {\mathsf {NC}^{1}^{1}\subseteq {\mathsf{NL}}\subseteq {\\mathsf {AC}}^{1}}}\subseteq {nc}^{2}\subseteq {p}}}.}$

NC 클래스는 AC 클래스와 관련이 있으며, AC 클래스는 유사하게 정의되지만 게이트에는 제한되지 않은 팬인이 있다. 나 한 명당, 우리는^[5][8]

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

이것의 즉각적인 결과로, 우리는 NC = AC를 가지게 되었다.^[9] 두 포함 모두 i = 0에 대해 엄격한 것으로 알려져 있다.^[5]

마찬가지로 NC는 O(log n) 공간과${\displaystyle }$(${\displaystyle \log }$ log${\displaystyle n{}^{}}$) ${\displaystyle O^{}}$ (${\displaystyle 1^{}}$) ${\$ n$)^{O(1)}$ 교대로$$ 각 단계에서 최대 2개의 옵션으로 제한된 교대 튜링 기계에서 해결 가능한 문제와 동등하다는 것을 알고 있다.^[10]

문제 열기: NC는 적절한가?

복잡성 이론의 한 가지 중요한 질문은 NC 계층의 모든 격납이 적절한가 하는 것이다. Papadimitriou는 NCⁱ = 일부 i의 경우ⁱ⁺¹ NCⁱ = NC, 모든 j = i의 경우 NC^j, 그 결과 NCⁱ = NC를 관측했다. 이러한 관찰을 NC-히어러제 붕괴라고 하는데, 이는 억제 연쇄에서 단 하나의 평등이라도 있기 때문이다.

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

전체 NC 계층이 어떤 레벨 i로 "붕괴"된다는 것을 암시한다. 따라서 두 가지 가능성이 있다.

1. ${\displaystyle {\mathsf {NC}^{1}\subset \cdots \subset \subset \subset \subset \subsets \subsetset \{nc}}}{ncdsetsf {\mathsf}}}}}}}}}}$
2. ${\displaystyle {\mathsf {NC}^{1}\subset \cdots \subset \subset \cdots \subset \subset \subset \subset \subsetset \subsetsubsetsetset \setsetset \\\\\\\subsetsubsubsubsetsubset \subs$

아직 두 진술의 진실에 관한 증거는 발견되지 않았지만 (1)이 사실이라는 것이 널리 알려져 있다.

NC⁰

특수 등급 NC는⁰ 입력 비트의 일정한 길이에서만 작동한다. 따라서 일정한 깊이와 경계가 있는 균일한 부울 회로에 의해 정의될 수 있는 기능의 등급으로 설명된다.

배링턴 정리

너비 k와 길이 m의 변수가 n개인 분기 프로그램은 m 명령의 순서에 따라 구성된다. 각각의 지시사항은 tuple (i, p, q)이고 여기서 i는 확인할 변수의 지수(1 ≤ i ≤ n)이며 p와 q는 {1, 2, ..., k}부터 {1, 2, ..., k}까지의 함수다. 번호 1, 2, ...k는 분기 프로그램의 상태라 불린다. 프로그램은 처음에 상태 1에서 시작되며, 각 명령(i, p, q)은 ith 변수가 0인지 1인지에 따라 x(x) 또는 q(x)로 상태를 변경한다. 프로그램의 최종 상태에 입력을 매핑하는 함수를 프로그램의 항복이라고 한다(더 정확히 말하면, 입력에 대한 항복은 해당 최종 상태에 초기 상태를 매핑하는 함수다. 프로그램에서는 가변 시퀀스 $x{\displaystyle {\mathrm{}}^{}}$ ${\$$displaystyle A\subset$ 2$^{$$n}}$이(가) F에 있을 때 정확히 A에 있도록$$ F${\displaystyle {setk}^{}}$ k$${\$displaystyle$ $F\$$subset$ k$^{$$k}}}}$의 일부 함수 세트가 있을 때 변수 값의 $세트{\displaystyle }$ A${\displaystyle {\mathrm{}}^{}}$ $2n을 받아들인다$.

분기 프로그램 패밀리는 각 n에 대해 n개의 변수를 갖는 분기 프로그램으로 구성된다. 그것은 n 변수 프로그램이 길이 n 입력으로 제한된 언어를 받아들일 때 언어를 받아들인다.

{0,1}의 모든 언어 L은 폭 5와 지수 길이의 분기 프로그램 패밀리 또는 지수 폭과 선형 길이의 패밀리로 인식될 수 있음을 쉽게 알 수 있다.

{0,1}의 모든 정규 언어는 일정한 폭과 선형 명령 수의 분기 프로그램 제품군에 의해 인식될 수 있다(DFA는 분기 프로그램으로 변환될 수 있기 때문이다). BWBP는 경계 폭과 다항 길이의 분기 프로그램 계열에서 인식할 수 있는 언어의 클래스를 의미한다.^[11]

Barrington의^[12] 정리에서는 BWBP가 정확히 통일되지 않은 NC라고¹ 말한다. 그 증거는 대칭 그룹 S의₅ 비확산성을 사용한다.^[11]

정리가 오히려 놀랍다. 예를 들어, 그것은 대부분의 함수가 일정한 폭과 다항식 크기의 분기 프로그램군에 의해 계산될 수 있다는 것을 암시하는 반면, 직관은 다항식 크기를 달성하기 위해서는 선형적인 수의 상태가 필요하다는 것을 암시할 수 있다.

배링턴 정리 증명

일정한 폭과 다항식 크기의 분기 프로그램은 NC의¹ 회로로 쉽게 변환할 수 있다.

반대로 NC에¹ 회로가 있다고 가정해 보자. 일반성을 상실하지 않는 한 게이트를 사용하지 않고 AND만 사용한다고 가정하십시오.

분기 프로그램 α-computing 회로 C가 다음과 같은 경우에 ID로 작동할 경우 C를 호출하십시오. C의 출력은 0이며 다음과 같다. α 할 때 C의 출력은 1이다.

Lemma 1의 결과로서 그리고 길이 5의 모든 사이클이 결합이라는 사실에 따라, 어떤 두 개의 5 사이클에 대해서도 α, β회로 C를 계산하는 분기 프로그램 α가 존재하는 경우, 동일한 길이의 회로 C를 계산하는 분기 프로그램 β가 존재한다.

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

메모들

참조

• Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.
• Clote, Peter; Kranakis, Evangelos (2002). Boolean functions and computation models. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 3-540-59436-1. Zbl 1016.94046.
• 그린로, 레이먼드, 제임스 후버, 월터 루조. 병렬 계산 한계: P-완성 이론. ISBN 0-19-508591-4
• Kozen, Dexter C. (1992). The design and analysis of algorithms. 강의 28 - 34 및 36
• Kozen, Dexter C. (2006). Theory of Computation. Texts in Computer Science. Springer-Verlag. ISBN 1-84628-297-7. Zbl 1102.68025. 강의 12: NC와 시간공간 수업의 관계
• Papadimitriou, Christos (1993). "Section 15.3: The class NC". Computational Complexity (1st ed.). Addison Wesley. pp. 375–381. ISBN 0-201-53082-1.
• Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. ISBN 3-7643-3719-2. Zbl 0816.68086.
• Vollmer, Heribert (1998). Introduction to circuit complexity. A uniform approach. Texts in Theoretical Computer Science. Berlin: Springer-Verlag. ISBN 3-540-64310-9. Zbl 0931.68055.