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

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

	กลุ่มที่ประกอบด้วยฟังก์ชันที่นับจำนวนคำตอบของเอ็นพี
	กลุ่มที่ยากที่สุดใน #P
	The arithmetic hierarchy
	that have approximation algorithms with constant approximation ratio
	สามารถตรวจสอบด้วยเกม ได้
	Solvable in polynomial time by randomized algorithms (answer is probably right)
	Solvable in polynomial time on a (answer is probably right)
	สามารถตรวจคำตอบของตัวอย่างที่ตอบว่า "ไม่ใช่" ได้อย่างมีประสิทธิภาพ
	กลุ่มที่ยากที่สุดในโค-เอ็นพี
	Solvable by a deterministic machine in space O(f(n)).
	Solvable by a deterministic machine in time O(f(n)).
	Solvable in exponential time with linear exponent
	The union of the classes in the
	ปัญหาที่แก้ได้โดยใช้พื้นที่ในการคำนวณเป็น ${\displaystyle 2^{O(n)}}$
	Solvable in exponential space
	The analogue of NP for
	The analogue of P for function problems
FP^NP	The analogue of P^NP for function problems; the home of the
	Fixed-parameter tractable
	Solvable in polynomial time by an
	Solvable in logarithmic (small) space
	Solvable in polynomial time by a
	Solvable efficiently (in polylogarithmic time) on parallel computers
	Solvable by a non-deterministic machine in exponential time with linear exponent
	Solvable by a non-deterministic machine in exponential space with linear exponent
	Same as NEXPTIME
	Solvable by a non-deterministic machine in exponential space
	Solvable by a non-deterministic machine in exponential time
	"YES" answers checkable in logarithmic space
	Complement of .
NP	คำตอบ "ใช่" ของปัญหาสามารถตรวจสอบได้ในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต
NP-complete	The hardest or most expressive problems in NP
	Analogue to P^NP for ; another name for FP^NP
	The hardest problems in FP^NP
	Either NP-complete or harder
	Solvable by a non-deterministic machine in space O(f(n)).
	Solvable by a non-deterministic machine in time O(f(n)).
P	หาคำตอบของปัญหาได้ภายในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต
	ปัญหาที่ยากที่สุดในพีในแง่ของการแก้ปัญหาด้วยการคำนวณแบบขนาน
	กลุ่มของปัญหาที่มองในรูปของคนตรวจสอบที่อ่านบทพิสูจน์แบบสุ่ม
	ลำดับชั้นของพหุนาม (polynomial hierarchy)
P^NP	Solvable in polynomial time with an for a problem in NP; also known as Δ2P
	Probabilistically Polynomial (answer is right with probability slightly more than ½)
	Solvable by recursively building up arithmetic functions.
	กลุ่มของปัญหาที่หาคำตอบได้โดยใช้เนื้อที่ไม่เกินฟังก์ชันพหุนามกับขนาดของอินพุต
	กลุ่มปัญหาที่ยากที่สุดในพีเสปซ
	Solvable in a finite amount of time.
	Problems to which we can answer "YES" in a finite amount of time, but a "NO" answer might never come.
	Solvable in logarithmic space by randomized algorithms (NO answer is probably right, YES is certainly right)
	Solvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right)
	Solvable in logarithmic space and polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right)
	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 .
	Unambiguous Non-Deterministic Polytime functions.
	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