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

หน้านี้ประกอบด้วยกลุ่มความซับซ้อนที่สำคัญทั้งหมดในด้านของทฤษฎีความซับซ้อนในการคำนวณ

#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	ปัญหาที่แก้ได้โดยใช้พื้นที่ในการคำนวณเป็น ${\displaystyle 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)

แหล่งข้อมูลอื่น

• Complexity Zoo เก็บถาวร 2006-11-28 ที่ เวย์แบ็กแมชชีน - list of over 400 complexity classes and their properties