Klasa złożoności
Z Wikipedii, wolnej encyclopedia
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 maszynie abstrakcyjnej 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 NC to zbiór problemów decyzyjnych, które można rozwiązać na równoległej maszynie RAM (maszynie PRAM) w czasie polilogarytmicznym przy użyciu wielomianowej liczby procesorów, a RP to klasa problemów, dla których istnieje probabilistyczna maszyna Turinga 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”