====== 복잡도 종류 ======

Complexity class. [[전산학]]에서 다루는 문제의 종류를 그 복잡도에 따라 분류한 집합. [[알고리즘분석]]과 [[계산이론]]의 주된 주제 중 하나이다.

여기서 말하는 "복잡도"라는 것은 매우 잘 정의된 개념으로, 어떤 문제의 복잡도는 그 문제를 특정한 종류의 [[계산모델]]로 풀 때 필요한 시간이나 공간을 가지고 결정된다. 예를 들어 [[외판원문제]](TSP)의 [[결정문제]] 버전은 [[비결정적튜링기계]]에서는 입력 크기의 [[다항식]]에 비례하는 시간([[다항시간]]) 안에 문제를 풀 수 있다는 게 알려져 있으며, 이를 복잡도 종류를 사용해서 표현하면 $$\mathrm{TSP} \in \mathbf{NP}$$라고 표현할 수 있다. 문제의 복잡도를 이런 식으로 분류하는 것은 여러 가지로 중요한데 이를테면 어떤 문제는 좀 더 단순한 (추상) 기계만으로 풀 수 있거나 훨씬 효율적으로 풀수 있다거나 하는 특성이 있기 때문이다.

전산학이나 [[프로그래밍]]을 하면서 볼 수 있는 대다수의 구체적인(([[인공지능]]같이 문제의 성격 자체가 구체적일 수 없는 경우를 빼고)) 문제들은 [[NP복잡도]]에 속하며, 그 중 많은 수가 [[P복잡도]]에 속한다는 것이 알려져 있다. (그러나 나머지가 정말로 P에 속하지 않는 건지는 아직 풀리지 않았다. [[P=NP]] 문제 참조.) [[촘스키위계]]와 같은 [[형식언어]]도 복잡도로 표현할 수 있다.

===== 목록 ===== 

  * [[P복잡도|P]]/[[FP복잡도|FP]] --- [[결정적튜링기계]]에서 [[다항시간]] 안에 풀 수 있는 [[결정문제]]/[[함수문제]]
  * [[NP복잡도|NP]]/[[FNP복잡도|FNP]] --- [[비결정적튜링기계]]에서 다항 시간 안에 "검증"할 수 있는 결정 문제/함수 문제
  * [[PSPACE복잡도]] --- 결정적 튜링 기계에서 다항 공간만큼만 써서 풀 수 있는 결정 문제 
  * [[BPP복잡도|BPP]]/[[BQP복잡도|BQP]] --- [[확률적튜링기계]]/[[양자튜링기계]]로 다항 시간 안에 0보다 큰 확률((0보다 크기만 하면 필요한 만큼 더 돌려서 무제한적으로 원하는 이상의 확률을 얻을 수 있다.))로 맞는 결과를 얻을 수 있는 결정 문제

===== 바깥 링크 =====

  * [[http://qwiki.stanford.edu/wiki/Complexity_Zoo|Complexity Zoo]] --- 수많은 복잡도 종류의 "동물원"

{{tag>전산학 목록}}