NC(복잡도)는 계산 복잡도 이론에서 중요한 복잡도 클래스 중 하나로, “Nick's Class”의 약자이다. 이는 컴퓨터 과학자 Nick Pippenger의 이름을 딴 것으로 추정되며, 병렬 컴퓨터에서 효율적으로 해결할 수 있는 결정 문제들의 집합을 나타낸다. 보다 정확히는, NC는 다항 시간에 해결할 수 있는 문제들 중에서 병렬화를 통해 매우 빠르게(즉, 다항 로그 시간 이내에) 해결할 수 있으며, 다항 개 이하의 프로세서를 사용하는 문제들의 복잡도 클래스이다.
형식적으로 NC는 다음과 같이 정의된다:
NC = ⋃ₖ NCₖ
여기서 NCₖ는 깊이 O((log n)ᵏ)이고, 크기가 다항식 크기(poly(n))인 제한된 크기의 논리 게이트 회로(Bounded fan-in Boolean circuit)로 결정할 수 있는 문제들의 클래스이다. 이는 균일(uniform)한 회로족으로 모델링되며, 각 문제의 인스턴스 크기에 따라 회로가 생성되는 방식이 효율적이어야 한다.
주요 특징 중 하나는 NC ⊆ P이며, NC가 P와 같은지 여부는 여전히 열린 문제이다. 만약 NC = P라면, 모든 다항 시간 문제는 매우 빠른 병렬 알고리즘을 가진다는 의미가 된다. 그러나 현재까지는 NC ≠ P라고 추측되는 경향이 있으며, 특히 NC에 포함되지 않는 것으로 여겨지는 P-완전 문제들이 존재한다(예: 선형 프로그래밍, 경로 탐색 문제 등).
NC는 병렬 컴퓨팅의 이론적 기반을 제공하며, 알고리즘 설계 시 병렬 처리 가능성 여부를 판단하는 기준으로 활용된다. 예를 들어, 정수의 덧셈, 곱셈, 행렬 곱셈 등 일부 기본 연산은 NC에 포함된다는 것이 증명되어 있다.
논의되는 하위 클래스로는 NC⁰, NC¹ 등이 있으며, NC⁰는 상수 깊이의 회로로 해결 가능한 제한된 문제들을 포함한다.
NC와 관련된 다른 복잡도 클래스로는 P, NP, L, NL, AC, TC 등이 있으며, 이들 사이의 포함 관계는 복잡도 이론의 주요 연구 주제 중 하나이다.