Klasa složenosti

Izvor: Wikipedija

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.

[uredi] Odnosi između klasa složenosti

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

[uredi] Daljnje čitanje

  • 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.

[uredi] Vidi i

  • Popis klasa složenosti