복잡도 종류

**복잡도 종류**(複雜度 種類)는 계산 복잡도 이론에서 계산 복잡도에 따라서 문제를 분류한 것이다. 복잡도 종류의 일반적 정의는 다음과 같은 형태로 되어 있다. 추상기계 M이 O(f(*n*)) 만큼의 자원 R을 이용하여 풀 수 있는 문제의 종류 (*n*은 입력의 길이) 예를 들어, NP는 확률적 튜링 기계가 다항시간에 풀 수 있는 판정 문제의 집합이고 PSPACE는 결정론적 튜링 기계가 다항공간에 풀 수 있는 판정 문제의 집합이다. 함수 문제의 집합인 FP 같은 것도 있다. 구체적인 계산모형 없이 복잡도 종류를 정의하는 데 사용할 수 있는 블럼 공리도 있다.
# 복잡도 종류 사이의 관계
아래 표는 복잡도 이론에서 다루는 문제(혹은 언어나 문법)의 종류를 정리한 것이다. 어떤 복잡도 종류 **X**가 **Y**의 진부분집합이면, **X**는 **Y** 아래에 검은 실선으로 연결했다. 만약 **X**가 **Y**의 부분집합이지만 두 집합이 같은지 아닌지 아직 알려지지 않았으면, 점선으로 연결했다. 엄밀하게 하자면 풀 수 있는 문제와 풀 수 없는 문제를 구분하는 것은 계산 복잡도 이론이 아니라 계산 가능성 이론에 속하지만, 전체적인 관계를 설명하기 위해 아래 표에 포함시켰다. {| cellpadding="0" cellspacing="0" border="0" align="center" |- align="center" | colspan="2" | || colspan="4" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%" |- | align="center" | 판정 문제 |} |- align="center" | colspan="2" | || | colspan="2" | || |- align="center" | colspan="3" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%" |- | align="center" | Type 0 (재귀 열거) |} | || colspan="4" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%" |- | align="center" | 판정 불가능 |} |- align="center" | colspan="3" | |- align="center" | colspan="3" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%" |- | align="center" | 판정 가능 |} |- align="center" | colspan="3" | |- align="center" | colspan="3" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%" |- | align="center" | EXPSPACE |} |- align="center" | colspan="3" | |- align="center" | colspan="3" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%" |- | align="center" | EXPTIME |} |- align="center" | colspan="3" | |- align="center" | colspan="8" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%" |- | align="center" | PSPACE |} |- align="center" | || width="40" | | || || | || || |- align="center" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%" |- | align="center" | Type 1 (문맥민감) |} | || | border="1" | || || | || colspan="1" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%" |- | align="center" | PSPACE-완전 |} |- align="center" | || | || || | |- align="center" | || | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%" |- | align="center" | co-NP |} | || || colspan="3" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%" |- | align="center" | NP |} |- align="center" | || | || || | || || |- align="center" | || | || {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%" |- | align="center" | BPP |} | width="10" | || {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%" |- | align="center" | BQP |} | width="10" | || {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%" |- | align="center" | NP-완전 |} |- align="center" | || | || || | |- align="center" | || | colspan="6" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%" |- | align="center" | P |} |- align="center" | || | | colspan="4" | || |- align="center" | || colspan="2" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%" |- | align="center" | NC |} | colspan="4" | || {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightGreen" width="100%" height="100%" |- | align="center" | P-완전 |} |- align="center" | || colspan="2" | |- align="center" | colspan="3" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%" |- | align="center" | Type 2 (문맥무관) |} |- align="center" | colspan="3" | |- align="center" | colspan="3" | {| cellpadding="0" cellspacing="0" border="1" bgcolor="lightBlue" width="100%" height="100%" |- | align="center" | Type 3 (정규) |} |}