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