Listo de klasoj de komplikeco

Ĉi tiu artikolo bezonas poluradon, ĉar ĝi montras stilajn kaj/aŭ gramatikajn kaj/aŭ strukturajn problemojn, kiuj ne konformas al stilogvido.

La priskribo de la problemo troviĝas ĉi tie. Bonvolu ŝanĝi la enhavon por plibonigi la artikolon.

Ĉ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
FP^NP	La analogo de P^NP 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 P^NP por funkciaj problemoj; alia nomo por FP^NP
NP-ekvivalenta	La plej malfacilaj problemoj en FP^NP
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
P^NP	Solvebla en polinoma tempo kun orakolo por problemo en NP; ankaŭ sciata kiel Δ₂P
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

Eksteraj ligiloj redakti

Arkivigite je 2006-11-28 per la retarkivo Wayback Machine. Zoo de komplikeco — listo de pli ol 400 komplikecaj klasoj kaj ties propraĵoj