Listo de klasoj de komplikeco

Ĉi tio estas listo de komplikecaj klasoj en komputa komplikteorio.

Multaj el ĉi tiuj klasoj havas asociitan Co-klason, kiu konsistas de la komplementoj de ĉiuj lingvoj de la originala klaso (??? vidu sube (Ĉi ...)). Ekzemple se L estas en NP, tiam la komplemento de L estas en Co-NP. Ĉi tio ne signifas, ke la komplemento de NP estas Co-NP — estas lingvoj kiuj estas sciataj esti ambaŭ, kaj aliaj lingvoj kiuj estas sciataj esti neniun.

La plej malfacilaj problemoj de klaso estas problemoj, kiuj apartenas la klaso kaj ĉiu alia problemo de tiu klaso povas reduktiĝi al ili. Plue, la malpligrandiĝo estas ankaŭ problemo de la donita klaso, aŭ ĝia subaro.

 #P  Komputo de solvaĵoj al NP problemo #P-plena  La plej malfacilaj problemoj en #P AH  La aritmetika hierarkio AP  La klaso de problemoj kiujn alterna maŝino de Turing povas solvi en polinoma tempo. APX  Optimumigo-problemoj, kiuj havas algoritmojn por proksimuma kalkulado kun konstanta proksimuma kalkulada rilatumo AM  Solvebla en polinoma tempo per protokolo de Arthur-Merlin BPP  Solvebla en polinoma tempo per hazardigitaj algoritmoj (respondo estas kredeble ĝusta) BQP  Solvebla en polinoma tempo sur kvantuma komputilo (respondo estas kredeble ĝusta) Co-NP  NE-aj respondoj estas kontroleblaj en polinoma tempo per ne-determinisma maŝino Co-NP-plena  La plej malfacilaj problemoj en Co-NP DSPACO(f(n))  Solvebla per determinisma maŝino en spaco O(f(n)) DTEMPO(f(n))  Solvebla per determinisma maŝino en tempo O(f(n)) E  Solvebla en eksponenta funkcia tempo kun lineara eksponento ELEMENTA  La unio de la klasoj en la eksponenta funkcia hierarkio ESPACO  Solvebla en eksponenta funkcia spaco kun lineara eksponento EKSP  Sama kiel EKSPTEMPO EKSPSPACO  Solvebla en eksponenta spaco EKSPTEMPO  Solvebla en eksponenta tempo FNP  La analogo de NP por funkciaj problemoj FP  La analogo de P por funkciaj problemoj FPNP  La analogo de PNP por funkciaj problemoj; la hejmo de la vojaĝa komiza problemo FPT  Fiksita-parametra akordiĝema IP  Solvebla en polinoma tempo per interaga pruva sistemo L  Solvebla en logaritma spaco (malgranda) MA  Solvebla en polinoma tempo per protokolo de Merlin-Arthur NC  Solvebla kompetente (en polilogaritma tempo) sur paralelaj komputiloj NE  Solvebla per ne-determinisma maŝino en eksponenta tempo kun lineara eksponento NESPACO  Solvebla per ne-determinisma maŝino en eksponenta spaco kun lineara eksponento NEKSP  Sama kiel NEKSPTEMPO NEKSPSPACO  Solvebla per ne-determinisma maŝino en eksponenta spaco NEXPTEMPO  Solvebla per ne-determinisma maŝino en eksponenta tempo NL  JES-aj respondoj kontroleblaj en logaritma spaco NEELEMENTA  Komplemento de ELEMENTA. NP  JES-aj respondoj estas kontroleblaj en polinoma tempo per ne-determinisma maŝino (vidu en komplikecaj klasoj P kaj NP) NP-plena  La plej malfacilaj aŭ plej esprimaj problemoj en NP NP-facila  Analoga al PNP por funkciaj problemoj; alia nomo por FPNP NP-ekvivalenta  La plej malfacilaj problemoj en FPNP NP-peza  NP-plena aŭ pli peza NSPACO(f(n))  Solvebla per ne-determinisma maŝino en spaco O(f(n)) NTEMPO(f(n))  Solvebla per ne-determinisma maŝino en tempo O(f(n)) P  Solvebla en polinoma tempo P-plena  La plej malfacilaj problemoj en P por solvi sur paralelaj komputiloj P/poli  Solvebla en polinoma tempo kun donita "konsila linio" dependanta nur de la enigo-amplekso PCP  Hazardisme kontrolebla pruvo PH  La unio de la klasoj en la polinoma hierarkio PNP  Solvebla en polinoma tempo kun orakolo por problemo en NP; ankaŭ sciata kiel Δ2P PP  Hazardisma polinoma (respondo estas ĝusta kun probablo malmulte pli granda ol 1/2) PR  Solvebla per rekursia konstruaĵo supren al aritmetikaj funkcioj PSPACO  Solvebla kun polinoma memoro kaj nelimigita tempo PSPACO-plena  La plej malfacilaj problemoj en PSPACO R  Solvebla en finia kvanto da tempo RE  Problemoj al kiuj oni povas respondi JES-e en finia kvanto da tempo, sed NE-a respondo povus neniam veni. RL  Solvebla en logaritma spaco per hazardigitaj algoritmoj (NE-a respondo estas kredeble ĝusta, JES estas certe ĝusta) RP  Solvebla en polinoma tempo per hazardigitaj algoritmoj (NE-a respondo estas kredeble ĝusta, JES estas certe ĝusta) RLP  Solvebla en logaritma spaco kaj polinoma tempo per hazardigitaj algoritmoj (NE-a respondo estas kredeble ĝusta, JES estas certe ĝusta) SL  Problemoj logaritmo-space reduktebla al determinisma se maniero ekzistas inter donitaj verticoj en sendirekta grafeo. En oktobro de 2004 estis esplorite, ke ĉi tiu klaso estas fakte egala al L. UP  Unusenca ne-determinisma polinomo-tempaj funkcioj. ZPP  Solvebla per hazardigitaj algoritmoj (respondo estas ĉiam ĝusta, averaĝa rultempo estas polinoma)

 Vidu ankaŭ 

 Komputada tempo
 Uzata memoro
 Komplikecaj klasoj P kaj NP
 Granda O

 Eksteraj ligiloj 
 . Zoo de komplikeco — listo de pli ol 400 komplikecaj klasoj kaj ties propraĵoj

Kategorio:Komputa komplikeco
Kategorio:Matematikaj listoj