복잡도 종류

1 개요

complexity class

복잡도 종류

• 계산 복잡도 이론에서 계산 복잡도에 따라서 문제를 분류한 것
• 추상기계 M이 O(f(n)) 만큼의 자원 R을 이용하여 풀 수 있는 문제의 종류 (n은 입력의 길이)

2 예시

• NP: 확률적 튜링 기계가 다항시간에 풀 수 있는 판정 문제의 집합
• PSPACE: 결정론적 튜링 기계가 다항공간에 풀 수 있는 판정 문제의 집합

3 참고

• https://ko.wikipedia.org/wiki/복잡도_종류
• https://ko.wikipedia.org/wiki/복잡도_종류_목록