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ŭ[redakti | redakti fonton]
Eksteraj ligiloj[redakti | redakti fonton]
- Arkivigite je 2006-11-28 per la retarkivo Wayback Machine. Zoo de komplikeco — listo de pli ol 400 komplikecaj klasoj kaj ties propraĵoj