복잡도 종류

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

복잡도 종류(複雜度 種類)는 계산 복잡도 이론에서 계산 복잡도에 따라서 문제를 분류한 것이다. 복잡도 종류의 일반적 정의는 다음과 같은 형태로 되어 있다.

추상기계 M이 O(f(n)) 만큼의 자원 R을 이용하여 풀 수 있는 문제의 종류 (n은 입력의 길이)

예를 들어, NP확률적 튜링 기계다항시간에 풀 수 있는 판정 문제의 집합이고 PSPACE결정론적 튜링 기계가 다항시간에 풀 수 있는 판정 문제의 집합이다. 함수 문제의 집합인 FP 같은 것도 있다.

구체적인 계산모형 없이 복잡도 종류를 정의하는 데 사용할 수 있는 블럼 공리도 있다.

복잡도 종류 사이의 관계[편집]

아래 표는 복잡도 이론에서 다루는 문제(혹은 언어나 문법)의 종류를 정리한 것이다. 어떤 복잡도 종류 XY진부분집합이면, XY 아래에 검은 실선으로 연결했다. 만약 XY의 부분집합이지만 두 집합이 같은지 아닌지 아직 알려지지 않았으면, 점선으로 연결했다. 엄밀하게 하자면 풀 수 있는 문제와 풀 수 없는 문제를 구분하는 것은 계산 복잡도 이론이 아니라 계산 가능성 이론에 속하지만, 전체적인 관계를 설명하기 위해 아래 표에 포함시켰다.


판정 문제
SolidLine.png SolidLine.png
Type 0 (재귀 열거)
판정 불가능
SolidLine.png
판정 가능
SolidLine.png
EXPSPACE
DottedLine.png
EXPTIME
DottedLine.png
PSPACE
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
Type 1 (문맥 민감)
SolidLine.png DottedLine.png DottedLine.png DottedLine.png
PSPACE-완전
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
co-NP
DottedLine.png
NP
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png DottedLine.png
BPP
BQP
NP-완전
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
P
SolidLine.png SolidLine.png DottedLine.png DottedLine.png
SolidLine.png
NC
P-완전
SolidLine.png SolidLine.png
Type 2 (문맥무관)
SolidLine.png
Type 3 (정규)

참고문헌[편집]

같이보기[편집]