Klasy złożoności Klasa złożoności to klasa zagadnień obliczeniowych o podobnej złożoności obliczeniowej – innymi słowy problemy, do których rozwiązania potrzebna jest podobna ilość zasobów, łączy się w klasy. Przykładowo mówi się o problemach o liniowej złożoności pamięciowej, jeśli ilość potrzebnej pamięci rośnie liniowo względem rozmiaru danych; czy też o problemach o kwadratowej złożoności czasowej, jeśli liczba operacji podstawowych rośnie z kwadratem rozmiaru danych. Podobne określenia stosuje się również do algorytmów.
Stosuje się też szersze pojęcia takie jak klasa P, czy NP, mając odpowiednio na uwadze decyzyjne problemy wielomianowe i decyzyjne problemy podlegające wielomianowej weryfikacji, jeśli odpowiedź jest twierdząca.
P vs NP
Pytanie, czy klasa P jest tym samym co NP, jest jednym z problemów milenijnych, za których rozwiązanie przewidziano nagrodę w wysokości 1 miliona dolarów. Każdy problem z klasy P jest również w klasie NP, nie wiadomo jednak, czy istnieją problemy klasy NP, które nie są problemami klasy P.
Są trzy możliwe rozwiązania: P = NP, P ≠ NP, Zagadnienie to jest w danej aksjomatyce teorii obliczeń nierozstrzygalne, czyli niezależne od aksjomatów.
Zobacz też problem komiwojażera algorytm in situ maszyna Turinga złożoność Kołmogorowa moc obliczeniowa