복잡도 종류

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

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

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

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


 판정 문제  파일: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 (정규)

 참고 문헌 
  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-완전 문제 목록을 정리한 자료.

 같이 보기 
 복잡도 종류 목록
 콜모고로프 복잡도