Complexity Zoo

GO8 – nhà cái trực tuyến uy tín mang đến trải nghiệm giải trí đỉnh cao cho người chơi đam mê cá cược. Với nền tảng công nghệ hiện đại, giao diện thân thiện và tốc độ xử lý mượt mà, GO8 cung cấp đa dạng trò chơi hấp dẫn như thể thao, casino, slot, bắn cá cùng nhiều ưu đãi thưởng lớn. Hệ thống bảo mật tiên tiến giúp người dùng an tâm tuyệt đối trong mọi giao dịch. Tham gia GO8 ngay hôm nay để tận hưởng thế giới giải trí an toàn, minh bạch và tràn đầy cơ hội chiến thắng. Website: https://go8.bz/

See Also

Introductory Resources

• Introductory Essay: New visitors may want to stop here and see what the Zoo is all about.
• Petting Zoo: A more gentle version of the Zoo with fewer classes, meant for new initiates in complexity. (If you're looking for where the Most Important Classes went, look in the Petting Zoo.)

Other Collections and Resources

• Complexity Garden: Problems of interest in complexity theory and some notes about important inclusions.
• Complexity Dojo: A collection of major theorems in complexity theory.
• Special Exhibit: A collection of classes of quantum states and probability distributions.
• Complexity Zoology: A computer-assisted survey maintained by the Greg Kuperberg, including active and static inclusion diagrams.
• Complexity Zoo for iPad (and iPhone): An iOS viewer for Complexity Zoo. An alternative.

Appendices

• Glossary: Definitions of some complexity theoretic terms.
• References: Bibliography for the Zoo.
• Pronunciation Guide: A resource for those who insist on communicating verbally about complexity.
• Conventions and Notation: Common notational conventions used here at the Zoo.
• Operators: A (very short) list of operators which act upon classes.
• Acknowledgments: Where the Zookeeper and friends acknowledge those who have helped out with the Zoo.
• Complexity Zoo Contributor's Guide: A guide on how to get started helping out with the Zoo.

NB: Longtime Zoo watchers may recall Chris Bourke's LaTeX version of the Zoo and Chad Brewbaker's graphical inclusion diagram. These references are obsolete until further notice.

All Classes

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

Symbols

0-1-NP_C - 1NAuxPDA^p - 2-EXP - 3SUM-hard - #AC⁰ - #L - #L/poly - #GA - #P - #W[t] - ⊕EXP - ⊕L - ⊕L/poly - ⊕P - ⊕P^cc - ⊕SAC⁰ - ⊕SAC¹

A

A₀PP - AC - AC⁰ - AC⁰[m] - AC¹ - ACC⁰ - Ack - AH - AL - ALL - ALOGTIME - AlgP/poly - Almost-NP - Almost-P - Almost-PSPACE - AM - AM^cc - AM_EXP - AM ∩ coAM - AM[polylog] - AmpMP - AmpP-BQP - AP - APP - APSPACE - APX - ASPACE - ATIME - AUC-SPACE(f(n)) - AuxPDA - AVBPP - AvgE - AvgP - AW[P] - AWPP - AW[SAT] - AW[*] - AW[t] - AxP - AxPP

B

βP - BC₌P - BH - BP_d(P) - BPE - BPEE - BP_HSPACE(f(n)) - BPL - BP•L - BP•NP - BPP - BPP^cc - BPP_{Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k}} ^cc - BPP^KT - BPP/log - BPP/mlog - BPP//log - BPP/rlog - BPP-OBDD - BPP_path - BPQP - BPSPACE(f(n)) - BPTIME(f(n)) - BQNC - BQNP - BQP - BQP/log - BQP/poly - BQP/mlog - BQP/mpoly - BQP/qlog - BQP/qpoly - BQP-OBDD - BQPSPACE - BQP_CTC - BQP_tt/poly - BQTIME(f(n)) - k-BWBP

C

C₌AC⁰ - C₌L - C₌P - CC - CC⁰ - CFL - CH - Check - C_kP - CL - CL#P - CLOG - CNP - coAM - coC₌P - cofrIP - Coh - coMA - coMod_kP - compIP - compNP - coNE - coNEXP - coNL - coNP - coNPC - coNP^cc - coNP/poly - coNQP - coRE - coRNC - coRP - coSL - coSPARSE - coUCC - coUP - CP - cq-Σ₂ - CSIZE(f(n)) - CSL - CSP - CSPACE - CZK

D

D#P - DCFL - Δ₂P - δ-BPP - δ-RP - DET - DiffAC⁰ - DisNP - DistNP - DP - DQC1 - DQP - DSPACE(f(n)) - DTIME(f(n)) - DTISP(t(n),s(n)) - Dyn-FO - Dyn-ThC⁰

E

E - EE - EEE - EESPACE - EEXP - EH - ELEMENTARY - EL_kP - EP - EPTAS - k-EQBP - EQP - EQP_K - EQTIME(f(n)) - ESPACE - ∃BPP - ∃NISZK - ∃R - EXP - EXP/poly - EXPSPACE

F

FBQP - FERT - FPERT - Few - FewEXP - FewP - FH - FIXP - FNL - FNL/poly - FNP - FO - FO(DTC) - FO(LFP) - FO(PFP) - FO(TC) - FO(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(n)} ) - FOLL - FP - FP^NP[log] - FPL - FPR - FPRAS - FPT - FPT_nu - FPT_su - FPTAS - FQMA - frIP - F-TAPE(f(n)) - F-TIME(f(n))

G

GA - GAN-SPACE(f(n)) - GapAC⁰ - GapL - GapP - GC(s(n),C) - GCSL - GI - GLO - GPCD(r(n),q(n)) - G[t]

H

HalfP - HeurBPP - HeurBPTIME(f(n)) - HeurDTIME_{Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta}} (f(n)) - HeurP - HeurPP - HeurNTIME_{Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta}} (f(n)) - H_kP - HVSZK

I

IC[log,poly] - IP - IOP - IPP - IP[polylog]

K

K

L

L - LC⁰ - LH - LIN - L_kP - LOGCFL - LogFew - LogFewNL - LOGLOG - LOGNP - LOGSNP - L/poly - LWPP

M

MA - MA^cc - MA' - MAC⁰ - MA_E - MA_EXP - mAL - MA_POLYLOG - MaxNP - MaxPB - MaxSNP - MaxSNP₀ - mcoNL - MinPB - MIP - MIP* - MIP^ns - MIP_EXP - (M_k)P - mL - MM - MMSNP - mNC¹ - mNL - mNP - Mod_kL - ModL - Mod_kP - ModP - ModPH - ModZ_kL - mP - MP - MPC - mP/poly - mTC⁰

N

NAuxPDA^p - NC - NC⁰ - NC¹ - NC² - NE - NE/poly - Nearly-P - NEE - NEEE - NEEXP - NEXP - NEXP/poly - NIPZK - NIQSZK - NISZK - NISZK_h - NL - NL/poly - NLIN - NLO - NLOG - NMCL - NONE - NNC(f(n)) - NP - NPC - NP_C - NP^cc - NP_{Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k}} ^cc - NPI - NP ∩ coNP - (NP ∩ coNP)/poly - NP/log - NPMV - NPMV-sel - NPMV_t - NPMV_t-sel - NPO - NPOPB - NP/poly - (NP,P-samplable) - NP_R - NPSPACE - NPSV - NPSV-sel - NPSV_t - NPSV_t-sel - NQL - NQL - NQP - NSPACE(f(n)) - NT - NT* - NTIME(f(n))

O

OIP - OMA - ONP - OptP - O₂P

P

P - P/log - P/poly - P^#P - P^#P[1] - P_CTC - PAC⁰ - PBP - k-PBP - P_C - P^cc - P_{Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k}} ^cc - PCD(r(n),q(n)) - P-Close - PCP(r(n),q(n)) - PDQP - PermUP - PEXP - PF - PFCHK(t(n)) - PH - PH^cc - Φ₂P - PhP - Π₂P - PINC - PIO - P^K - PKC - PL - PL₁ - PL_∞ - PLF - PLL - P-LOCAL - P-RLOCAL - PLS - P^NP - P^NPcc - P^||NP - P^NP[k] - P^NP[log] - P^{NP[log^2]} - P-OBDD - PODN - polyL - PostBPP - PostBPP^cc - PostBQP - PP - PP^cc - PP/poly - PPA - PPAD - PPADS - P^PP - PPP - PPSPACE - P^QMA[log] - PQUERY - PR - P_R - Pr_HSPACE(f(n)) - PromiseBPP - PromiseBQP - PromiseP - PromiseRP - PromiseUP - PrSPACE(f(n)) - P-Sel - PSK - PSPACE - PSPACE^cc - PSPACE/poly - PT₁ - PTAPE - PTAS - PT/WK(f(n),g(n)) - PureSuperQMA - PZK

Q

Q - QAC⁰ - QAC⁰[m] - QACC⁰ - QAC_f⁰ - QAM - QCFL - QCMA - QCPH - QEPH - QH - QIP - QIP[2] - QL - QMA - QMA-plus - QMA⁺ - QMA(2) - QMA₁ - QMA_log - QMA⁺(2) - QMAM - QMA/qpoly - QMIP - QMIP_le - QMIP_ne - QNC - QNC⁰ - QNC⁰/qpoly - QNC⁰/🐱 - QNC_f⁰ - QNC¹ - QP - QPH - QPLIN - QPSPACE - qq-QAM - QRG - QRG(k) - QRG(2) - QRG(1) - QRL - QSZK

R

R - RBQP - RE - REG - RevSPACE(f(n)) - RG - RG[1] - R_HL - R_HSPACE(f(n)) - RL - RNC - RNC¹ - RP - RP^cc - RP_{Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k}} ^cc - RPP - RQP - RSPACE(f(n))

S

S^≠ - S₂P - S₂E - S₂-EXP•P^NP - SAC - SAC⁰ - SAC¹ - SAPTIME - SBP - SBP^cc - SBQP - SC - SE - SEH - SelfNP - SF_k - Σ₂P - SIZE(f(n)) - SKC - SL - SLICEWISE PSPACE - SNP - SO - SO(Horn) - SO(Krom) - SO(LFP) - SO(TC) - SO[Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t(n)} ] - SP - span-L - span-P - SPARSE - SPL - SPP - SQG - StoqMA - SUBEXP - symP - SZK - SZK_h

T

TALLY - TC - TC⁰ - TC⁰(FOLL) - TC¹ - TFNP - Θ₂P - TI - TOWER - TreeBQP - TREE-REGULAR

U

UAM^cc - UAP - UCC - UCFL - UE - UL - UL/poly - UP - UP^cc - UPostBPP^cc - UPP^cc - US - USBP^cc - UWAPP^cc

V

VC_k - VC_OR - VNC_k - VNP_k - VP_k - VPL - VQP_k

W

W[1] - WAPP - WAPP^cc - WHILE - W[P] - WPP - W[SAT] - W[*] - W[t] - W^*[t]

X

XOR-MIP*[2,1] - XL - XNL - XP - XP_uniform

Y

YACC - YP - YPP - YQP

Z

ZAM^cc - ZBQP - ZK - ZPE - ZP•L - ZPP - ZPP^cc - ZPTIME(f(n)) - ZQP