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

หน้านี้ประกอบด้วยกลุ่มความซับซ้อนที่สำคัญทั้งหมดในด้านของทฤษฎีความซับซ้อนในการคำนวณ
| --- | --- |
#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 Δ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)