Klasa složenosti
From Wikipedia, the free encyclopedia
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.