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
รายการกล, มความซ, บซ, อน, บทความน, องการการจ, ดหน, ดหมวดหม, ใส, งก, ภายใน, หร, อเก, บกวาดเน, อหา, ให, ณภาพด, ณสามารถปร, บปร, งแก, ไขบทความน, ได, และนำป, ายออก, จารณาใช, ายข, อความอ, นเพ, อช, ดข, อบกพร, องหน, าน, ประกอบด, วยกล, มความซ, บซ, อนท, สำค, ญท, งหมดในด. bthkhwamnitxngkarkarcdhna cdhmwdhmu islingkphayin hruxekbkwadenuxha ihmikhunphaphdikhun khunsamarthprbprungaekikhbthkhwamniid aelanapayxxk phicarnaichpaykhxkhwamxunephuxchichdkhxbkphrxnghnaniprakxbdwyklumkhwamsbsxnthisakhythnghmdindankhxngthvsdikhwamsbsxninkarkhanwn P klumthiprakxbdwyfngkchnthinbcanwnkhatxbkhxngexnphi P complete klumthiyakthisudin PAH The arithmetic hierarchyAPX Optimization problems that have approximation algorithms with constant approximation ratioAM samarthtrwcsxbdwyekmxarethxr emxrlin idBPP 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 samarthtrwckhatxbkhxngtwxyangthitxbwa imich idxyangmiprasiththiphaphCo NP complete klumthiyakthisudinokh exnphiDSPACE 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 exponentELEMENTARY The union of the classes in the exponential hierarchyESPACE pyhathiaekidodyichphunthiinkarkhanwnepn 2 O n displaystyle 2 O n EXPEXPSPACE Solvable in exponential spaceFNP The analogue of NP for function problemsFP The analogue of P for function problemsFPNP The analogue of PNP for function problems the home of the traveling salesman problemFPT Fixed parameter tractableIP Solvable in polynomial time by an interactive proof systemL Solvable in logarithmic small spaceMA Solvable in polynomial time by a Merlin Arthur protocolNC Solvable efficiently in polylogarithmic time on parallel computersNE Solvable by a non deterministic machine in exponential time with linear exponentNESPACE Solvable by a non deterministic machine in exponential space with linear exponentNEXP Same as NEXPTIMENEXPSPACE Solvable by a non deterministic machine in exponential spaceNEXPTIME Solvable by a non deterministic machine in exponential timeNL YES answers checkable in logarithmic spaceNONELEMENTARY Complement of ELEMENTARY NP khatxb ich khxngpyhasamarthtrwcsxbidinewlathiepnfngkchnphhunamkbkhnadkhxngxinphutNP complete The hardest or most expressive problems in NPNP easy Analogue to PNP for function problems another name for FPNPNP equivalent The hardest problems in FPNPNP hard Either NP complete or harderNSPACE 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 hakhatxbkhxngpyhaidphayinewlathiepnfngkchnphhunamkbkhnadkhxngxinphutP complete pyhathiyakthisudinphiinaengkhxngkaraekpyhadwykarkhanwnaebbkhnanPCP klumkhxngpyhathimxnginrupkhxngkhntrwcsxbthixanbthphisucnaebbsumPH ladbchnkhxngphhunam polynomial hierarchy PNP Solvable in polynomial time with an oracle for a problem in NP also known as D2PPP Probabilistically Polynomial answer is right with probability slightly more than PR Solvable by recursively building up arithmetic functions PSPACE klumkhxngpyhathihakhatxbidodyichenuxthiimekinfngkchnphhunamkbkhnadkhxngxinphutPSPACE complete klumpyhathiyakthisudinphiespsR 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 aehlngkhxmulxun aekikhComplexity Zoo list of over 400 complexity classes and their properties bthkhwamniyngepnokhrng khunsamarthchwywikiphiediyidodyephimkhxmulekhathungcak https th wikipedia org w index php title raykarklumkhwamsbsxn amp oldid 9360096, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
