กลุ่มความซับซ้อน - วิกิพีเดีย

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

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

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

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

## [แก้] External link

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

ดึงข้อมูลจาก "http://th.wikipedia.org../../../%E0%B8%81/%E0%B8%A5/%E0%B8%B8/%E0%B8%81%E0%B8%A5%E0%B8%B8%E0%B9%88%E0%B8%A1%E0%B8%84%E0%B8%A7%E0%B8%B2%E0%B8%A1%E0%B8%8B%E0%B8%B1%E0%B8%9A%E0%B8%8B%E0%B9%89%E0%B8%AD%E0%B8%99.html".

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

##### Views

- บทความ
- อภิปราย
- รุ่นปัจจุบัน

##### ค้นหา

##### ภาษาอื่น

- Deutsch
- English
- Español
- Italiano