Liste over kompleksitetsklasser - List of complexity classes

Dette er en liste over kompleksitetsklasser i beregningskompleksitetsteori . For andre emner innen beregning og kompleksitet, se liste over emner for beregning og kompleksitet .

Mange av disse klassene har en "co" -partner som består av komplementene til alle språk i den opprinnelige klassen. For eksempel hvis et språk L er i NP, er komplementet til L i co-NP. (Dette betyr ikke at komplementet til NP er co-NP - det er språk som er kjent for å være i begge, og andre språk som er kjent for å være på ingen av dem.)

"De vanskeligste problemene" i en klasse refererer til problemer som tilhører klassen slik at alle andre problemer i den klassen kan reduseres til den. Videre er reduksjonen også et problem for den gitte klassen, eller dens undergruppe.

#P Telle løsninger på et NP-problem
# P-komplett De vanskeligste problemene i #P
2-EXPTIME Løselig på dobbelt eksponentiell tid
AC 0 En kretsskompleksitetsklasse med begrenset dybde
ACC 0 En kretsskompleksitetsklasse med avgrenset dybde og tellende porter
AC En kretsskompleksitetsklasse
AH Det aritmetiske hierarkiet
AP Klassen av problemer som veksler mellom Turing-maskiner kan løse på polynomisk tid.
APX Optimaliseringsproblemer som har tilnærmelsesalgoritmer med konstant tilnærmingsforhold
ER Løselig i polynomisk tid av en Arthur – Merlin-protokoll
BPP Løselig i polynomtid med randomiserte algoritmer (svaret er sannsynligvis riktig)
BQP Løselig i polynomtid på en kvantecomputer (svaret er sannsynligvis riktig)
co-NP "NEI" svar som kan kontrolleres i polynomisk tid av en ikke-deterministisk maskin
co-NP-komplett De vanskeligste problemene i co-NP
DSPACE (f ( n )) Løses av en deterministisk maskin med mellomrom O (f ( n )).
DTIME (f ( n )) Løses av en deterministisk maskin i tid O (f ( n )).
E Løselig i eksponentiell tid med lineær eksponent
ELEMENTÆR Foreningen av klassene i det eksponensielle hierarkiet
ESPACE Løselig med eksponentiell plass med lineær eksponent
EXP Samme som EXPTIME
UTSETT Løselig med eksponentiell plass
EXPTIME Løselig på eksponentiell tid
FNP Analogen av NP for funksjonsproblemer
FP Analogen av P for funksjonsproblemer
FP NP Analogen av P NP for funksjonsproblemer; hjemmet til det omreisende selgerproblemet
FPT Fastparameter som kan spores
GapL Logspace-reduserbar for beregning av heltallsdeterminanten til en matrise
IP Løselig i polynomisk tid med et interaktivt bevis system
L Løselig med logaritmisk (liten) plass
LOGCFL Logspace-reduserbar til et kontekstfritt språk
MA Løselig i polynomisk tid ved en Merlin – Arthur-protokoll
NC Løses effektivt (på polylogaritmisk tid) på parallelle datamaskiner
NE Løses av en ikke-deterministisk maskin i eksponentiell tid med lineær eksponent
NESPACE Løses av en ikke-deterministisk maskin med eksponentiell plass med lineær eksponent
NESTE Samme som NESTE
NEXPSPACE Løses av en ikke-deterministisk maskin med eksponentiell plass
NESTE TID Løses av en ikke-deterministisk maskin på eksponentiell tid
NL "JA" svar kan kontrolleres med logaritmisk plass
NONELEMENTARY Utfylling av ELEMENTARY .
NP "JA" svar kan kontrolleres i polynomisk tid (se kompleksitetsklassene P og NP )
NP-komplett De vanskeligste eller mest uttrykksfulle problemene i NP
NP-lett Analog til P NP for funksjonsproblemer ; et annet navn for FP NP
NP-ekvivalent De vanskeligste problemene i FP NP
NP-hard Minst like vanskelig som alle problemer i NP, men ikke kjent for å være i samme kompleksitetsklasse
NSPACE (f ( n )) Løses av en ikke-deterministisk maskin med mellomrom O (f ( n )).
NTIME (f ( n )) Løses av en ikke-deterministisk maskin i tid O (f ( n )).
P Løselig på polynomisk tid
P-komplett De vanskeligste problemene i P å løse på parallelle datamaskiner
P / poly Løselig på polynomisk tid gitt en "rådsstreng", avhengig bare av inngangsstørrelsen
PCP Probabilistisk kontrollerbart bevis
PH Foreningen av klassene i polynomhierarkiet
P NP Løselig i polynomisk tid med et orakel for et problem i NP; også kjent som Δ 2 P
PP Probabilistically Polynomial (svaret er riktig med sannsynlighet litt over ½)
PPAD Argumenter for polynomsparitet på dirigerte grafer
PR Løses ved rekursivt å bygge opp aritmetiske funksjoner.
PSPACE Løselig med polynomrom.
PSPACE-komplett De vanskeligste problemene i PSPACE.
PTAS Tilnærmingsskjema for polynomtid (en underklasse av APX).
QIP Løselig i polynomisk tid med et kvantuminteraktivt bevis system.
QMA Kvanteanalog av NP .
R Løselig på en begrenset tid.
RE Problemer som vi kan svare "JA" på i en begrenset periode, men et "NEI" svar kommer kanskje aldri.
RL Løselig med logaritmisk plass ved randomiserte algoritmer (INGEN svar er sannsynligvis riktig, JA er absolutt riktig)
RP Løselig i polynomtid med randomiserte algoritmer (INGEN svar er sannsynligvis riktig, JA er absolutt riktig)
SL Problemer med log-space kan reduseres for å avgjøre om det finnes en bane mellom gitte hjørner i en ikke-rettet graf. I oktober 2004 ble det oppdaget at denne klassen er faktisk lik L .
S 2 P en runde spill med samtidige trekk dømt deterministisk i polynomisk tid
TFNP Totale funksjonsproblemer som kan løses i ikke-deterministisk polynomtid. Et problem i denne klassen har den egenskapen at hver inngang har en utgang hvis gyldighet kan kontrolleres effektivt, og beregningsutfordringen er å finne en gyldig utgang.
OPP Entydige ikke-bestemte Polytime-funksjoner.
ZPL Løses av randomiserte algoritmer (svaret er alltid riktig, gjennomsnittlig plassbruk er logaritmisk)
ZPP Løses av randomiserte algoritmer (svaret er alltid riktig, gjennomsnittlig kjøretid er polynom)

Referanser

Eksterne linker

  • Complexity Zoo - liste over over 500 kompleksitetsklasser og deres egenskaper