NC(Nick's Class)는 계산 복잡도 이론에서 정의되는 복잡도 종류(complexity class) 중 하나로, 다항 개의 프로세서를 갖춘 병렬 컴퓨터가 다항로그(polylogarithmic) 시간 내에 판정할 수 있는 판정 문제들의 집합을 가리킨다. 구체적으로, 입력 크기가 n인 문제가 NC에 속한다는 것은 상수 c와 k가 존재하여, O(n^k)개의 병렬 프로세서를 사용하여 O(log^c n) 시간 안에 해당 문제를 풀 수 있음을 의미한다.
이름의 유래와 관련하여, NC라는 명칭은 컴퓨터 과학자 닉 피펜저(Nick Pippenger)의 이름에서 따온 것으로 알려져 있다. 피펜저는 크기는 크지만 깊이가 얕은 회로에 대한 연구를 수행했으며, 이는 효율적인 병렬화가 가능한 프로그램의 개념과 대응한다. 스티븐 쿡(Stephen Cook)이 이 이름을 붙인 것으로 전해진다.
NC의 정의에서 병렬 컴퓨터는 병렬 임의 접근 기계(PRAM, Parallel Random Access Machine)로 간주할 수 있다. PRAM은 공유 메모리를 사용하는 병렬 컴퓨터 모델로, 어떤 프로세서도 메모리의 임의의 비트에 상수 시간에 접근할 수 있다. NC의 정의는 여러 프로세서가 동시에 한 비트에 접근하는 방식을 어떻게 제어하는지(CRCW, CREW, EREW 등)에 영향을 받지 않는다.
NC는 회로 복잡도 관점에서도 동등하게 정의될 수 있다. 즉, NC는 다항로그 깊이(polylogarithmic depth)를 가지며 게이트 수가 다항 개인 균일 불 회로(uniform Boolean circuit)로 판정할 수 있는 판정 문제들의 집합으로도 표현된다.
NC는 계층 구조를 가지며, NC^i는 게이트가 다항 개이고 깊이가 O(log^i n)인 균일 불 회로로 판정할 수 있는 판정 문제들의 복잡도 종류로 정의된다. 즉, 프로세서가 다항 개인 병렬 컴퓨터로 O(log^i n) 시간에 풀 수 있는 판정 문제들의 집합이다.
NC와 다른 복잡도 종류 사이의 관계에 대해서는 다음과 같은 사실이 알려져 있다. P를 결정론적 튜링 기계가 다룰 수 있는 문제들의 집합으로 볼 때, 병렬 컴퓨터는 순차 컴퓨터로 시뮬레이션할 수 있으므로 NC는 P의 부분집합이다. NC = P인지 여부는 아직 밝혀지지 않은 미해결 문제이며, 학계에서는 이 명제가 거짓일 것으로 추정하고 있다. 즉, 본래 순차적이어서 병렬화를 통해 빠르게 처리할 수 없는 문제가 존재할 것이라는 견해가 지배적이다. 이와 유사하게, P-완전(P-complete) 문제는 "병렬화할 수 없을 것 같은" 문제로 간주된다.
공간 복잡도 종류와의 관계로는, 크리스토스 파파디미트리우(Christos Papadimitriou)의 저서 《계산 복잡도》에 제시된 정리에 따르면 다음의 포함 관계가 성립한다.
NC^1 ⊆ L ⊆ NL ⊆ NC^2
여기서 L은 로그 공간(log space) 복잡도 종류, NL은 비결정적 로그 공간(nondeterministic log space) 복잡도 종류를 나타낸다.
또한 NC^i는 교대 튜링 기계(alternating Turing machine)가 O(log n) 공간을 사용하고 log^O(1) n만큼 교대(alternation)를 수행하여 풀 수 있는 문제들의 집합과 동일한 것으로 알려져 있다.
NC는 병렬 계산의 이론적 기초를 이루는 중요한 복잡도 종류로, 정수 연산, 행렬 연산 등 병렬화에 적합한 다양한 문제들이 NC에 속하는 것으로 알려져 있다. NC 계층의 적절성(properness), 즉 NC^i가 NC^(i+1)의 진부분집합인지 여부는 현재까지 밝혀지지 않은 중요한 미해결 문제이다.
