klasa złożoności

Klasa złożoności – zbiór problemów obliczeniowych o podobnej złożoności obliczeniowej. Najbardziej pospolitą definicją klasy złożoności jest: Zbiór problemów, które mogą być rozwiązane na M przy użyciu O(f(n)) zasobu R, gdzie n jest rozmiarem wejścia. Na przykład klasa P to zbiór problemów decyzyjnych, które można rozwiązać na maszynie Turinga w czasie wielomianowym natomiast klasa NP to zbiór problemów decyzyjnych, które można rozwiązać na niedeterministycznej maszynie Turinga w czasie wielomianowym. Z kolei klasa to zbiór problemów decyzyjnych, które można rozwiązać na równoległej maszynie RAM w czasie polilogarytmicznym przy użyciu wielomianowej liczby procesorów, a to klasa problemów, dla których istnieje działająca w czasie wielomianowym, która zwraca „nie” zawsze, kiedy prawidłową odpowiedzią jest „nie”, i zwraca „tak” (z prawdopodobieństwem, które dla żadnych danych nie spada poniżej pewnej wartości) lub „nie”, kiedy prawidłową odpowiedzią jest „tak”