NC (복잡도) 문서 원본 보기

{{위키데이터 속성 추적}}
[[계산 복잡도 이론]]에서 '''NC'''(Nick's Class)는 프로세서가 다항 개인 [[병렬 컴퓨터]]가 다항로그 시간에 판정할 수 있는 [[판정 문제]]의 집합이다. 다시 말해서, 어떤 문제가 '''NC'''라는 것은, 이 문제를 상수 <math>c</math>와 <math>k</math>에 대해서 병렬 프로세서 <math>O(n^k)</math>개를 써서 <math>O(\log^c n)</math>시간에 풀 수 있다는 뜻이다. [[스티븐 쿡]]은 회로를 다항로그 깊이와 다항 크기에 대해서 연구를 많이 한 [[닉 피펜저]]의 이름을 따서 {{lang|en|'''N'''ick's '''C'''lass|닉 클래스}}라는 이름을 지었다.

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

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

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

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

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

<math> \mathbf{NC_1 \subseteq L \subseteq NL \subseteq NC_2} </math>

이와 비슷하게, <math>\mathbf{NC}^i</math>는 [[교대 튜링 기계]]가 <math>O(\log n)</math> 공간을 쓰고 <math>\log ^{O(1)} n</math>만큼 교대를 해서 풀 수 있는 문제의 집합과 같다.

== 참고 문헌 ==

* Greenlaw, Raymond, James Hoover, and Walter Ruzzo. ''Limits To Parallel computation; P-Completeness Theory''. {{ISBN|0-19-508591-4}}
* Heribert Vollmer. ''[https://web.archive.org/web/20061231011947/http://www.thi.uni-hannover.de/forschung/publikationen/cc/index.en.php Introduction to Circuit Complexity -- A Uniform Approach]''. {{ISBN|3-540-64310-9}}
* {{서적 인용|저자 = [[크리스토스 파파디미트리우]] | 연도 = 1994 | 제목 = Computational Complexity |url = https://archive.org/details/computationalcom0000papa | 출판사 = Addison Wesley | 판 = 1판 |ISBN=0-201-53082-1| 장 = 15.3: 복잡도 종류 '''NC''' | 페이지 = [https://archive.org/details/computationalcom0000papa/page/375 375]-381}}
* {{서적 인용|저자 = [[덱스터 코젠]] | 연도 = 2006 | 제목 = Theory of Computation |url = https://archive.org/details/theoryofcomputat0000koze | 출판사 = Springer |ISBN=1-84628-297-7| 장=12: ''NC''와 시공간 복잡도 종류의 관계({{lang|en|Relation of ''NC'' to Time-Space Classes}}) }}

{{복잡도 종류}}

[[분류:복잡도 종류]]
[[분류:회로 복잡도]]