NC (복잡도)

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

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

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

[편집] 참고문헌


주요 복잡도 종류 (더 보기)

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

다른 언어