NC (복잡도)

위키백과 ― 우리 모두의 백과사전.

계산 복잡도 이론에서 NC(Nick's Class)는 프로세서가 다항 개인 병렬 컴퓨터가 다항로그 시간에 판정할 수 있는 판정 문제의 집합이다. 다시 말해서, 어떤 문제가 NC라는 것은, 이 문제를 상수 c와 k에 대해서 병렬 프로세서 O(n^k)개를 써서 O((log n)^c)시간에 풀 수 있다는 뜻이다. 스티븐 쿡은 회로를 다항로그 깊이와 다항 크기에 대해서 연구를 많이 한 닉 피펜저의 이름을 따서 Nick's class 닉 클래스라는 이름을 지었다.

P를 결정론적 튜링 기계가 다룰 수 있는 문제들로 보는 것과 마찬가지로, NC도 병렬 컴퓨터가 효율 있게 다룰 수 있는 문제로 볼 수 있다. 병렬 컴퓨터는 순차 컴퓨터가 시뮬레이트할 수 있기 때문에 NC는 P의 부분집합이다. NC = P인지는 아직 밝혀지지 않았지만, 학계에서는 이 명제가 거짓일 것으로 보고 있다. "본래 순차"이기 때문에 병렬화해서 빠르게 할 수 없는 문제가 존재할 것이라는 뜻이다. NP-완전을 "다룰 수 없을 것 같은" 문제로 보는 것과 같다. 따라서 P-완전도 "병렬화할 수 없을 것 같은", "본래 순차일 것 같은" 문제로 생각할 수 있다.

이 정의에서 병렬 컴퓨터는 병렬이고 임의로 접근할 수 있는 기계(PRAM)라고 볼 수 있다. 이 기계는 메모리를 공유하는 병렬 컴퓨터로, 어떤 프로세서도 메모리에 있는 임의의 비트를 상수 시간에 접근할 수 있다. NC의 정의는 PRAM이 여러 프로세서가 동시에 한 비트에 접근하는 방법을 어떻게 제어하는지에 영향을 받지 않는다. 그 방법에는 CRCW, CREW, EREW 등이 있다. 이러한 모델에 대한 설명은 PRAM을 참고하라.

이와 동등하게 NC는 다항로그 깊이에 게이트가 다항개인 균일 불 회로가 판정할 수 있는 판정 문제들로 정의할 수 있다.

NCⁱ는 게이트가 다항개이고 깊이가 O((log n)ⁱ)인 균일 불 회로로 판정할 수 있는 판정 문제의 복잡도 종류이다. 즉, 프로세서가 다항개인 병렬 컴퓨터로 O((log n)ⁱ) 시간에 풀 수 있는 판정 문제의 집합이다.

NC를 공간 복잡도인 L and NL와 관련지을 수 있다. 크리스토스 파파디미트리우가 지은 《계산 복잡도》에 나오는 정리 16.1에 따르면 다음 관계가 성립한다고 한다.

이와 비슷하게, NCⁱ는 교대 튜링 기계가 O(log n) 공간을 쓰고 (log n)^O(1)만큼 교대를 해서 풀 수 있는 문제의 집합과 같다.

[편집] 참고문헌

• Greenlaw, Raymond, James Hoover, and Walter Ruzzo. Limits To Parallel computation; P-Completeness Theory. ISBN 0-19-508591-4
• Heribert Vollmer. Introduction to Circuit Complexity -- A Uniform Approach. ISBN 3-540-64310-9
• 크리스토스 파파디미트리우 (1994). "15.3: 복잡도 종류 NC", Computational Complexity, 1판, Addison Wesley, 375-381. ISBN 0-201-53082-1.
• 덱스터 코젠 (2006). "12: NC와 시공간 복잡도 종류의 관계(Relation of NC to Time-Space Classes)", Theory of Computation. Springer. ISBN 1-84628-297-7.

v · d · e  주요 복잡도 종류 (더 보기)
P · NP · co-NP · NP-C · co-NP-C · NP-난해 · UP · #P · #P-C · L · NL · NC · P-C · PSPACE · PSPACE-C · EXPTIME · EXPSPACE · PR · RE · co-RE · RE-C · co-RE-C · R · BQP · BPP · RP · ZPP · PCP · IP · PH