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

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

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

หมวดหมู่:ทฤษฎีความซับซ้อนในการคำนวณ
*