Klasa složenosti

U računskoj teoriji složenosti, klasa složenosti je skup problema povezane složenosti. Tipična je klasa složenosti sljedećeg oblika:

skup problema rješivih apstraktnim strojem M koristeći O(f(n)) resursa R (n je veličina ulaza)

Na primjer, klasa NP je skup svih problema odluke koji mogu biti riješeni nedeterminističkim Turingovim strojem u polinomnom vremenu, dok je klasa PSPACE skup svih problema odluke koji mogu biti riješeni determinističkim Turingovim strojem u polinomnom prostoru. Neke su klase složenosti skupovi funkcijskih problema, kao što je FP.

Mnoge se klase složenosti mogu karakterizirati matematičkom logikom potrebnom za njihov opis, vidi deskriptivna složenost.

Blumovi aksiomi se mogu rabiti za definiranje klasa složenosti bez referiranja na neki konkrentni računski model.

Odnosi između klasa složenosti

uredi

Sljedeća tablica pokazuje neke klase problema (ili jezika, ili gramatika) koji se razmatraju u teoriji složenosti. Ako je klasa X pravi podskup od Y, tada je X dolje prikazan ispod Y, pri čemu ih povezuje tamna linija. Ako je X podskup, ali se ne zna jesu li skupovi jednaki, tada je linija svjetlija i točkasta. Tehnički, podjela u odlučive i neodlučive probleme više potpada u teoriju izračunljivosti, ali i pomaže u pružanju perspektive nad klasama složenosti.

Problem odluke
   
Tip 0 (Rekurzivno prebrojiv)
Neodlučiv
 
Odlučiv
 
EXPSPACE
 
EXPTIME
 
PSPACE
           
Tip 1 (Kontekstno ovisan)
       
PSPACE-potpun
         
   
Co-NP
   
NP
           
     
BPP
BQP
NP-potpun
         
   
P
       
 
NC
P-potpun
   
Tip 2 (Kontekstno neovisan)
 
Tip 3 (Regularan)

Daljnje čitanje

uredi

Vidi još

uredi