복잡도 종류

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

“

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

”

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

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

복잡도 종류 사이의 관계

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

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

참고 문헌

• (영어) The Complexity Zoo: 복잡도 종류에 대한 방대한 자료
• (영어) Neil Immerman이 만든 복잡도 종류 사이의 관계도
• 마이클 게리, 데이비드 S. 존슨: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. NP-완전 문제 목록을 정리한 자료.

같이 보기

• 복잡도 종류 목록
• 콜모고로프 복잡도