NC (복잡도)
위키백과 ― 우리 모두의 백과사전.
계산 복잡도 이론에서 NC(Nick's Class)는 프로세서가 다항 개인 병렬 컴퓨터가 다항로그 시간에 판정할 수 있는 판정 문제의 집합이다. 다시 말해서, 어떤 문제가 NC라는 것은, 이 문제를 상수 c와 k에 대해서 병렬 프로세서 O(nk)개를 써서 O((log n)c)시간에 풀 수 있다는 뜻이다. 스티븐 쿡은 회로를 다항로그 깊이와 다항 크기에 대해서 연구를 많이 한 닉 피펜저의 이름을 따서 Nick's class 닉 클래스라는 이름을 지었다.
P를 결정론적 튜링 기계가 다룰 수 있는 문제들로 보는 것과 마찬가지로, NC도 병렬 컴퓨터가 효율 있게 다룰 수 있는 문제로 볼 수 있다. 병렬 컴퓨터는 순차 컴퓨터가 시뮬레이트할 수 있기 때문에 NC는 P의 부분집합이다. NC = P인지는 아직 밝혀지지 않았지만, 학계에서는 이 명제가 거짓일 것으로 보고 있다. "본래 순차"이기 때문에 병렬화해서 빠르게 할 수 없는 문제가 존재할 것이라는 뜻이다. NP-완전을 "다룰 수 없을 것 같은" 문제로 보는 것과 같다. 따라서 P-완전도 "병렬화할 수 없을 것 같은", "본래 순차일 것 같은" 문제로 생각할 수 있다.
[편집] 참고문헌
- 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.
| 주요 복잡도 종류 (더 보기) |
|---|
|
P | NP | co-NP | NP-C | co-NP-C | NP-난해 | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C |
