복잡도 종류

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

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

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

목록

바깥 링크

1) 인공지능같이 문제의 성격 자체가 구체적일 수 없는 경우를 빼고
2) 0보다 크기만 하면 필요한 만큼 더 돌려서 무제한적으로 원하는 이상의 확률을 얻을 수 있다.

도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-09-05 07:08 | 작성자 lifthrasiir