복잡도 종류 목록

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

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

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

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

#P	NP 문제의 해 개수를 세는 문제.
#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	지수가 선형인 지수 공간을 써서 풀 수 있는 문제.
EXP	EXPTIME과 같다.
EXPSPACE	지수 공간을 써서 풀 수 있는 문제.
EXPTIME	지수 시간을 써서 풀 수 있는 문제.
FNP	NP의 함수 문제판
FP	P의 함수 문제판
FPNP	PNP의 함수 문제판. 외판원 문제가 여기 속한다.
FPT	고정-인자 트랙터블(tractable).
IP	대화형 증명 체계로 다항 시간에 풀 수 있는 문제.
L	로그 공간을 써서 풀 수 있는 문제.
LOGCFL	문맥무관 언어로 로그공간-환산을 할 수 있는 문제
MA	멀린-아서 프로토콜을 통해 다항 시간에 풀 수 있는 문제.
NC	병렬 컴퓨터에서 다항로그 시간에 잘 풀 수 있는 문제.
NE	비결정론적 기계에서 지수가 선형인 지수 시간을 써서 풀 수 있는 문제.
NESPACE	비결정론적 기계에서 지수가 선형인 지수 공간을 써서 풀 수 있는 문제.
NEXP	NEXPTIME과 같다.
NEXPSPACE	비결정론적 기계로 지수 공간에 풀 수 있는 문제.
NEXPTIME	비결정론적 기계로 지수 시간에 풀 수 있는 문제.
NL	"예" 답이 맞는지를 로그 공간을 써서 확인할 수 있는 문제.
NONELEMENTARY	ELEMENTARY의 여집합.
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	다항 위계에 들어 있는 복잡도 종류의 합집합.
PNP	NP 문제에 대한 신탁의 도움을 받아 다항 시간에 풀 수 있는 문제. Δ2P라고도 한다.
PP	확률적 다항. (답은 ½보다 조금 큰 확률로 맞다.)
PR	수론 함수를 귀납적으로 쌓아 풀 수 있는 문제.
PSPACE	다항 기억 공간과 무한한 시간이 주어졌을 때 풀 수 있는 문제.
PSPACE-complete	PSPACE에서 가장 어려운 문제.
R	유한한 시간에 풀 수 있는 문제.
RE	"예" 답은 유한 시간에 할 수 있고 "아니오" 답은 영원히 못 할 수도 있는 문제.
RL	확률적 알고리즘으로 로그 공간을 써서 풀 수 있는 문제. (아니오 답은 확률적으로 맞고, 예 답은 언제나 맞다.)
RP	확률적 알고리즘으로 다항 시간에 풀 수 있는 문제. (아니오 답은 확률적으로 맞고, 예 답은 언제나 맞다.)
RLP	확률적 알고리즘으로 로그 공간을 써서 다항 시간에 풀 수 있는 문제. (아니오 답은 확률적으로 맞고, 예 답은 언제나 맞다.)
SL	무향 그래프에서 꼭짓점 사이에 길이 있는지를 판정하는 문제로 로그공간-환산을 할 수 있는 문제. L과 같다.
UP	비결정론적 기계가 다항 시간에 모호하지 않은 경로로 푸는 문제.
ZPP	확률적 알고리즘으로 풀 수 있는 문제.(답은 항상 맞고, 평균 실행 시간은 다항 시간이다.)

외부 링크

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