Klasa složenosti

Izvor: Wikipedija
Skoči na: orijentacija, traži

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 VE | 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
SolidLine.png SolidLine.png
Tip 0 (Rekurzivno prebrojiv)
Neodlučiv
SolidLine.png
Odlučiv
SolidLine.png
EXPSPACE
DottedLine.png
EXPTIME
DottedLine.png
PSPACE
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
Tip 1 (Kontekstno ovisan)
SolidLine.png DottedLine.png DottedLine.png DottedLine.png
PSPACE-potpun
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
Co-NP
DottedLine.png DottedLine.png
NP
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png DottedLine.png
BPP
BQP
NP-potpun
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
P
SolidLine.png SolidLine.png DottedLine.png DottedLine.png
SolidLine.png
NC
P-potpun
SolidLine.png SolidLine.png
Tip 2 (Kontekstno neovisan)
SolidLine.png
Tip 3 (Regularan)

Daljnje čitanje[uredi VE | uredi]

  • The Complexity Zoo: Ogromni popis klasa složenosti, kao referenca za eksperte.
  • Dijagram Neila Immermana koji prikazuje hijerarhiju klasa složenosti i kako se one nadopunjuju.
  • Michael Garey i David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. Standardna referenca za NP-potpune probleme - važne kategorije problema čija rješenja naizgled zahtijevaju nepraktično mnogo vremena za računanje.

Vidi još[uredi VE | uredi]