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

จากวิกิพีเดีย สารานุกรมเสรี

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

#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)

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

  • Complexity Zoo - list of over 400 complexity classes and their properties