รายการกลุ่มความซับซ้อน

หน้านี้ประกอบด้วยกลุ่มความซับซ้อนที่สำคัญทั้งหมดในด้านของทฤษฎีความซับซ้อนในการคำนวณ
{|
| #P || กลุ่มที่ประกอบด้วยฟังก์ชันที่นับจำนวนคำตอบของเอ็นพี
|-
| #P-complete || กลุ่มที่ยากที่สุดใน #P
|-
| AH || The arithmetic hierarchy
|-
| APX || Optimization problems that have approximation algorithms with constant approximation ratio
|-
| AM || สามารถตรวจสอบด้วยเกมอาร์เธอร์-เมอร์ลิน ได้
|-
| BPP || Solvable in polynomial time by randomized algorithms (answer is probably right)
|-
| BQP || Solvable in polynomial time on a quantum computer (answer is probably right)
|-
| Co-NP || สามารถตรวจคำตอบของตัวอย่างที่ตอบว่า "ไม่ใช่" ได้อย่างมีประสิทธิภาพ
|-
|  Co-NP-complete || กลุ่มที่ยากที่สุดในโค-เอ็นพี
|-
| DSPACE(f(n)) || Solvable by a deterministic machine in space O(f(n)).
|-
| DTIME(f(n)) || Solvable by a deterministic machine in time O(f(n)).
|-
| E || Solvable in exponential time with linear exponent
|-
| ELEMENTARY || The union of the classes in the exponential hierarchy
|-
|  ESPACE || ปัญหาที่แก้ได้โดยใช้พื้นที่ในการคำนวณเป็น 2^{O(n)}
|-
| EXP ||
|-
| EXPSPACE || Solvable in exponential space
|-
| FNP || The analogue of NP for function problems
|-
| FP || The analogue of P for function problems
|-
| FPNP || The analogue of PNP for function problems; the home of the traveling salesman problem
|-
| FPT || Fixed-parameter tractable
|-
| IP || Solvable in polynomial time by an interactive proof system
|-
| L || Solvable in logarithmic (small) space
|-
| MA || Solvable in polynomial time by a Merlin-Arthur protocol
|-
| NC || Solvable efficiently (in polylogarithmic time) on parallel computers
|-
| NE || Solvable by a non-deterministic machine in exponential time with linear exponent
|-
| NESPACE || Solvable by a non-deterministic machine in exponential space with linear exponent
|-
| NEXP || Same as NEXPTIME
|-
| NEXPSPACE || Solvable by a non-deterministic machine in exponential space
|-
| NEXPTIME || Solvable by a non-deterministic machine in exponential time
|-
| NL || "YES" answers checkable in logarithmic space
|-
| NONELEMENTARY || Complement of ELEMENTARY.
|-
| NP || คำตอบ "ใช่" ของปัญหาสามารถตรวจสอบได้ในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต
|-
| NP-complete || The hardest or most expressive problems in NP
|-
| NP-easy || Analogue to PNP for function problems; another name for FPNP
|-
| NP-equivalent || The hardest problems in FPNP
|-
| NP-hard || Either NP-complete or harder
|-
| NSPACE(f(n)) || Solvable by a non-deterministic machine in space O(f(n)).
|-
| NTIME(f(n)) || Solvable by a non-deterministic machine in time O(f(n)).
|-
| P || หาคำตอบของปัญหาได้ภายในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต
|-
|  P-complete || ปัญหาที่ยากที่สุดในพีในแง่ของการแก้ปัญหาด้วยการคำนวณแบบขนาน
|-
| PCP || กลุ่มของปัญหาที่มองในรูปของคนตรวจสอบที่อ่านบทพิสูจน์แบบสุ่ม
|-
| PH || ลำดับชั้นของพหุนาม (polynomial hierarchy)
|-
| PNP || Solvable in polynomial time with an oracle for a problem in NP; also known as &Delta;2P
|-
| PP || Probabilistically Polynomial (answer is right with probability slightly more than ½)
|-
| PR || Solvable by recursively building up arithmetic functions.
|-
| PSPACE || กลุ่มของปัญหาที่หาคำตอบได้โดยใช้เนื้อที่ไม่เกินฟังก์ชันพหุนามกับขนาดของอินพุต
|-
| PSPACE-complete || กลุ่มปัญหาที่ยากที่สุดในพีเสปซ
|-
| R || Solvable in a finite amount of time.
|-
| RE || Problems to which we can answer "YES" in a finite amount of time, but a "NO" answer might never come.
|-
| RL || Solvable in logarithmic space by randomized algorithms (NO answer is probably right, YES is certainly right)
|-
| RP || Solvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right)
|-
| RLP || Solvable in logarithmic space and polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right)
|-
| SL || Problems log-space reducible to determining if a path exist between given vertices in an undirected graph. In October 2004 it was discovered that this class is in fact equal to L.
|-
| UP || Unambiguous Non-Deterministic Polytime functions.
|-
| ZPP || Solvable by randomized algorithms (answer is always right, average running time is polynomial)
|}
== แหล่งข้อมูลอื่น ==
Complexity Zoo  - list of over 400 complexity classes and their properties
ทฤษฎีความซับซ้อนในการคำนวณ
*