Liste over kompleksitetsklasser - List of complexity classes
Dette er en liste over kompleksitetsklasser i beregningskompleksitetsteori . For andre beregnings- og kompleksitetsemner, se liste over emner, der kan beregnes og kompleksitet .
Mange af disse klasser har en 'co' partner, der består af komplementerne til alle sprog i den originale klasse. For eksempel, hvis et sprog L er i NP, så er komplementet af L i co-NP. (Dette betyder ikke, at komplementet til NP er co-NP - der er sprog, der vides at være på begge dele, og andre sprog, som man ved, er i ingen af dem.)
"De sværeste problemer" i en klasse henviser til problemer, der hører til klassen, således at ethvert andet problem i den klasse kan reduceres til den. Desuden er reduktionen også et problem for den givne klasse eller dens delmængde.
#P | Tæl løsninger på et NP-problem |
# P-komplet | De sværeste problemer i #P |
2-UDLØBELSE | Løselig i dobbelt eksponentiel tid |
AC 0 | En kredsløbskompleksitetsklasse med afgrænset dybde |
ACC 0 | En kredsløbskompleksitetsklasse med afgrænset dybde og tælleporte |
AC | En kredsløbskompleksitetsklasse |
AH | Det aritmetiske hierarki |
AP | Klassen af problemer, der skifter Turing-maskiner, kan løse på polynomisk tid. |
APX | Optimeringsproblemer, der har tilnærmelsesalgoritmer med konstant tilnærmelsesforhold |
ER | Løselig i polynomisk tid med en Arthur – Merlin-protokol |
BPP | Løselig i polynomisk tid ved hjælp af randomiserede algoritmer (svaret er sandsynligvis rigtigt) |
BQP | Løselig i polynomisk tid på en kvantecomputer (svaret er sandsynligvis rigtigt) |
co-NP | "NEJ" svar kan kontrolleres på polynomisk tid af en ikke-deterministisk maskine |
co-NP-komplet | De sværeste problemer i co-NP |
DSPACE (f ( n )) | Løselig med en deterministisk maskine med mellemrum O (f ( n )). |
DTIME (f ( n )) | Løselig med en deterministisk maskine i tiden O (f ( n )). |
E | Løselig i eksponentiel tid med lineær eksponent |
ELEMENTÆRE | Foreningen af klasserne i det eksponentielle hierarki |
RUM | Løselig med eksponentielt rum med lineær eksponent |
EXP | Samme som EXPTIME |
EKSPACE | Løselig med eksponentielt rum |
UDLØB | Løselig i eksponentiel tid |
FNP | Analogen af NP til funktionsproblemer |
FP | Analogen af P til funktionsproblemer |
FP NP | Analogen af P NP til funktionsproblemer; hjemsted for den rejsende sælgerproblem |
FPT | Fast-parameter trækkelig |
GapL | Logspace-reducerbar til beregning af en matrixs heltalsdeterminant |
IP | Løselig i polynomisk tid af et interaktivt bevis system |
L | Løselig med logaritmisk (lille) plads |
LOGCFL | Log-plads-reducerbar til et kontekstfrit sprog |
MA | Løselig i polynomisk tid ved hjælp af en Merlin – Arthur-protokol |
NC | Kan løses effektivt (på polylogaritmisk tid) på parallelle computere |
NE | Løselig af en ikke-deterministisk maskine i eksponentiel tid med lineær eksponent |
NESPACE | Løselig med en ikke-deterministisk maskine med eksponentielt rum med lineær eksponent |
NEXP | Samme som NÆSTE |
NEXPSPACE | Løselig med en ikke-deterministisk maskine med eksponentiel plads |
NÆSTE TID | Løselig af en ikke-deterministisk maskine i eksponentiel tid |
NL | "JA" svar kan kontrolleres med logaritmisk mellemrum |
NONELEMENTÆR | Supplering af ELEMENTARY . |
NP | "JA" svar kan kontrolleres i polynomisk tid (se kompleksitetsklasser P og NP ) |
NP-komplet | De sværeste eller mest udtryksfulde problemer i NP |
NP-let | Analog til P NP for funktionsproblemer ; et andet navn for FP NP |
NP-ækvivalent | De sværeste problemer i FP NP |
NP-hård | Mindst lige så hårdt som ethvert problem i NP, men ikke kendt for at være i samme kompleksitetsklasse |
NSPACE (f ( n )) | Løselig med en ikke-deterministisk maskine med mellemrum O (f ( n )). |
NTIME (f ( n )) | Løselig med en ikke-deterministisk maskine i tiden O (f ( n )). |
P | Løselig i polynomisk tid |
P-komplet | De sværeste problemer i P at løse på parallelle computere |
P / poly | Løselig på polynomisk tid givet en "rådgivningsstreng", afhængigt kun af inputstørrelsen |
PCP | Bevis, der sandsynligvis kan kontrolleres |
PH | Foreningen af klasserne i polynomhierarkiet |
P NP | Løselig i polynomisk tid med et orakel for et problem i NP; også kendt som Δ 2 P |
PP | Probabilistically Polynomial (svaret er rigtigt med sandsynligheden lidt mere end ½) |
PPAD | Argumenter for polynomsparitet på instruerede grafer |
PR | Løselig ved rekursiv opbygning af aritmetiske funktioner. |
PSPACE | Løselig med polynomisk rum. |
PSPACE-komplet | De sværeste problemer i PSPACE. |
PTAS | Polynomial-time tilnærmelsesplan (en underklasse af APX). |
QIP | Løselig i polynomisk tid af et kvanteinteraktivt bevis system. |
QMA | Kvanteanalog af NP . |
R | Løselig på en begrænset tid. |
RE | Problemer, som vi kan svare "JA" på i en begrænset periode, men et "NEJ" svar kommer måske aldrig. |
RL | Løselig med logaritmisk plads ved hjælp af randomiserede algoritmer (INGEN svar er sandsynligvis rigtigt, JA er bestemt rigtigt) |
RP | Løselig i polynomisk tid ved hjælp af randomiserede algoritmer (INGEN svar er sandsynligvis rigtigt, JA er bestemt rigtigt) |
SL | Problemer med log-plads kan reduceres til bestemmelse af, om der findes en sti mellem givne hjørner i en ikke-rettet graf. I oktober 2004 blev det opdaget, at denne klasse er faktisk lig med L . |
S 2 P | en runde spil med samtidige træk dømt deterministisk i polynomisk tid |
TFNP | Samlede funktionsproblemer, der kan løses i ikke-deterministisk polynomisk tid. Et problem i denne klasse har den egenskab, at hvert input har et output, hvis gyldighed kan kontrolleres effektivt, og den beregningsmæssige udfordring er at finde et gyldigt output. |
OP | Utvetydige ikke-deterministiske polytime-funktioner. |
ZPL | Løselig med randomiserede algoritmer (svaret er altid rigtigt, gennemsnitlig pladsforbrug er logaritmisk) |
ZPP | Kan løses ved hjælp af randomiserede algoritmer (svaret er altid korrekt, den gennemsnitlige kørselstid er polynom) |
Referencer
eksterne links
- Complexity Zoo - liste over over 500 kompleksitetsklasser og deres egenskaber