복잡도 종류 목록

이 문서는 계산 복잡도 이론에서 다루는 복잡도 종류 목록이다. 다른 계산·복잡도 관련 내용이 궁금하면 계산 가능성과 복잡도 관련 주제 목록을 보자.

복잡도 종류 가운데 원래 종류에 들어 있는 모든 언어의 보완()으로 이루어진 'co'짝이 있는 종류가 많다. 예를 들어 어떤 언어 L이 NP에 들어 있으면 L의 보완은 co-NP에 들어 있다. (이건 NP의 보완이 co-NP라는 뜻은 아니다. 둘 다에 들어 있는 언어도 있고, 어느 쪽에도 들어 있지 않은 언어도 있다.)

복잡도 종류에서 "가장 어려운 문제"는 같은 종류에 들어 있는 문제라면 모두 그 문제로 환산할 수 있는 문제를 말한다. 환산을 하는 문제 자체도 그 종류에 들어 있거나, 그 종류의 부분집합에 들어 있다.

목록에 없는 문제가 있다면, 짝을 찾아 보면 된다. 이를테면 co-UP가 궁금하면 UP를 본다.

#PNP 문제의 해 개수를 세는 문제.#P-완전#P에서 가장 어려운 문제.AH산술 위계.AP교대 튜링 기계가 다항 시간에 풀 수 있는 문제.APX상수 비율 근사 알고리즘이 있는 최적화 문제.AM아서-멀린 프로토콜을 통해 다항 시간에 풀 수 있는 문제.BPP확률적 알고리즘으로 다항 시간에 풀 수 있는 문제 (답은 일정 확률로 바르게 나온다)BQP양자 컴퓨터로 다항 시간에 풀 수 있는 문제 (답은 일정 확률로 바르게 나온다)co-NP비결정론적 튜링기계가 다항 시간에 "아니오" 답이 맞는지 확인할 수 있는 문제.co-NP-완전co-NP에서 가장 어려운 문제.DSPACE(f(n))결정론적 기계가 O(f(n)) 공간을 써서 풀 수 있는 문제.DTIME(f(n))결정론적 기계가 O(f(n)) 시간에 풀 수 있는 문제..E지수가 선형인 지수 시간에 풀 수 있는 문제.ELEMENTARY지수 위계에 있는 복잡도 종류의 합집합ESPACE지수가 선형인 지수 공간을 써서 풀 수 있는 문제.EXPEXPTIME과 같다.EXPSPACE지수 공간을 써서 풀 수 있는 문제.EXPTIME지수 시간을 써서 풀 수 있는 문제.FNPNP의 함수 문제판FPP의 함수 문제판FPNPPNP의 함수 문제판. 외판원 문제가 여기 속한다.FPT고정-인자 트랙터블().IP대화형 증명 체계로 다항 시간에 풀 수 있는 문제.L로그 공간을 써서 풀 수 있는 문제.LOGCFL 문맥무관 언어로 로그공간-환산을 할 수 있는 문제MA멀린-아서 프로토콜을 통해 다항 시간에 풀 수 있는 문제.NC병렬 컴퓨터에서 다항로그 시간에 잘 풀 수 있는 문제.NE비결정론적 기계에서 지수가 선형인 지수 시간을 써서 풀 수 있는 문제.NESPACE비결정론적 기계에서 지수가 선형인 지수 공간을 써서 풀 수 있는 문제.NEXPNEXPTIME과 같다.NEXPSPACE비결정론적 기계로 지수 공간에 풀 수 있는 문제.NEXPTIME비결정론적 기계로 지수 시간에 풀 수 있는 문제.NL"예" 답이 맞는지를 로그 공간을 써서 확인할 수 있는 문제.NONELEMENTARYELEMENTARY의 여집합.NP비결정론적 기계에서 "예" 답이 맞는지를 다항 시간에 확인할 수 있는 문제. (참고: P-NP 문제)NP-완전NP 가운데 어렵고 의미 있는 문제.NP-쉬움PNP의 함수 문제판. FPNP의 다른 이름.NP-동등FPNP에서 가장 어려운 문제.NP-난해NP-완전이거나 더 어려운 문제.NSPACE(f(n))비결정론적 기계로 O(f(n))공간에 풀 수 있는 문제.NTIME(f(n))비결정론적 기계로 O(f(n))시간에 풀 수 있는 문제.P다항 시간에 풀 수 있는 문제.P-완전P 문제 중 병렬 컴퓨터로 풀기 어려운 문제.P/poly입력 크기에 좌우되는 "조언 문자열"이 주어질 때 다항 시간에 풀 수 있는 문제.PCP확률적으로 검사 가능한 증명.PH다항 위계에 들어 있는 복잡도 종류의 합집합.PNPNP 문제에 대한 신탁의 도움을 받아 다항 시간에 풀 수 있는 문제. Δ2P라고도 한다.PP확률적 다항. (답은 ½보다 조금 큰 확률로 맞다.)PR수론 함수를 귀납적으로 쌓아 풀 수 있는 문제.PSPACE다항 기억 공간과 무한한 시간이 주어졌을 때 풀 수 있는 문제.PSPACE-completePSPACE에서 가장 어려운 문제.R유한한 시간에 풀 수 있는 문제.RE"예" 답은 유한 시간에 할 수 있고 "아니오" 답은 영원히 못 할 수도 있는 문제.RL확률적 알고리즘으로 로그 공간을 써서 풀 수 있는 문제. (아니오 답은 확률적으로 맞고, 예 답은 언제나 맞다.)RP확률적 알고리즘으로 다항 시간에 풀 수 있는 문제. (아니오 답은 확률적으로 맞고, 예 답은 언제나 맞다.)RLP확률적 알고리즘으로 로그 공간을 써서 다항 시간에 풀 수 있는 문제. (아니오 답은 확률적으로 맞고, 예 답은 언제나 맞다.)SL무향 그래프에서 꼭짓점 사이에 길이 있는지를 판정하는 문제로 로그공간-환산을 할 수 있는 문제. L과 같다.UP비결정론적 기계가 다항 시간에 모호하지 않은 경로로 푸는 문제.ZPP확률적 알고리즘으로 풀 수 있는 문제.(답은 항상 맞고, 평균 실행 시간은 다항 시간이다.)

 외부 링크 
  복잡도 동물원(The Complexity Zoo) - 400개가 넘는 복잡도 종류와 그 성질을 모아놓은 곳

*