Listo de klasoj de komplikeco

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

Ĉ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ŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]