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
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)

[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 još

• Popis klasa složenosti