범주:복잡도 클래스

• 복잡도 등급

*

• 복잡도 클래스 목록
• 계산성 및 복잡성 항목 목록

♯

• ♯P

0–9

• 2-EXPTIME

A

• AC(복잡성)
• AC0
• ACC0
• 전체(복잡성)
• APX
• 산술 계층 구조

C

• CC(복잡성)
• Co-NP
• Co-NP-완전
• Co-RE
• Co-RE-완전

D

• DLOGTIME
• 디스페이스
• 디타임

E

• E(복잡성)
• 초등
• 에스페이스
• 지수 계층 구조
• 엑스포스페이스
• 엑스트라타임

F

• FL(복잡성)
• FNP(복잡성)
• FP(복잡성)
• FPT(복잡성 클래스)
• 완전 다항식 시간 근사 구성표

G

• GapP
• GI(복잡성)
• GI-완전

L

• L(복잡성)
• L/폴리
• LH(복잡성)
• LOGCFL

N

• NC(복잡성)
• NE(복잡성)
• NEXPTIME
• NL(복잡성)
• NL-완전
• 일차적인 문제
• NP(복잡성)
• NP-완전성
• NP-Easy
• NP등가
• NP-강경성
• NP중간
• NP/폴리
• NSpace
• NTIME

P

• P(복잡성)
• P/폴리
• P-완전
• 패리티 P
• PH(복잡성)
• PLS(복잡성)
• 폴리엘
• 다항식 시간 근사 체계
• PPA(복잡성)
• PPAD(복잡성)
• PPP(복잡성)
• PR(복잡성)
• 의사-폴리놈 시간
• 의사-폴리놈 변환
• 프스페이스
• PSpace-완전
• PSpace-hard

Q

• 준폴리네멀 타임

R

• R(복잡성)
• 랜덤 액세스 튜링 머신
• RE(복잡성)
• 재완성

S

• S2P(복잡성)
• SC(복잡성)
• ♯P-완전
• SL(복잡성)
• SNP(복잡성)
• 강한 NP-완전성
• SUBEXP

T

• TC(복잡성)
• TC0
• TFNP

U

• UP(복잡성)

W

• W 계층 구조
• 약한 NP-완전성

X

• XP(복잡성 클래스)