복잡도 종류
복잡도 종류(複雜度 種類)는 계산 복잡도 이론에서 계산 복잡도에 따라서 문제를 분류한 것이다. 복잡도 종류의 일반적 정의는 다음과 같은 형태로 되어 있다.
| “ | 추상기계 M이 O(f(n)) 만큼의 자원 R을 이용하여 풀 수 있는 문제의 종류 (n은 입력의 길이) | ” |
예를 들어, NP는 확률적 튜링 기계가 다항시간에 풀 수 있는 판정 문제의 집합이고 PSPACE는 결정론적 튜링 기계가 다항공간에 풀 수 있는 판정 문제의 집합이다. 함수 문제의 집합인 FP 같은 것도 있다.
복잡도 종류 사이의 관계
[편집]아래 표는 복잡도 이론에서 다루는 문제(혹은 언어나 문법)의 종류를 정리한 것이다. 어떤 복잡도 종류 X가 Y의 진부분집합이면, X는 Y 아래에 검은 실선으로 연결했다. 만약 X가 Y의 부분집합이지만 두 집합이 같은지 아닌지 아직 알려지지 않았으면, 점선으로 연결했다. 엄밀하게 하자면 풀 수 있는 문제와 풀 수 없는 문제를 구분하는 것은 계산 복잡도 이론이 아니라 계산 가능성 이론에 속하지만, 전체적인 관계를 설명하기 위해 아래 표에 포함시켰다.
| ||||||||||
 |
| |||||||||
|
| |||||||||
| ||||||||||
| ||||||||||
| ||||||||||
| ||||||||||
 | ||||||||||
| ||||||||||
| ||||||||||
| ||||||||||
| |
| | | | |||||
|
| |
| |
| |||||
| |
| | | ||||||
| |
|
|
| ||||||
| |
| | | | |||||
| |
|
|
|
| |||||
| |
| | | ||||||
| |
| ||||||||
| |
|
| |||||||
|
|
| ||||||||
| | |||||||||
| ||||||||||
| ||||||||||
| ||||||||||
참고 문헌
[편집]- (영어) 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-완전 문제 목록을 정리한 자료.