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 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”
Ważne klasy złożoności
Wiele ważnych klas złożoności można zdefiniować przez ograniczenie czasu lub miejsca, na które zapotrzebowanie ma algorytm. Należą do nich:
| Klasa złożoności | Model obliczeń | Ograniczenie zasobów |
|---|---|---|
| DTIME(f(n)) | Deterministyczna maszyna Turinga | Czas f(n) |
| P | Deterministyczna maszyna Turinga | Czas poly(n) |
| EXPTIME | Deterministyczna maszyna Turinga | Czas 2poly(n) |
| NTIME(f(n)) | Niedeterministyczna maszyna Turinga | Czas f(n) |
| NP | Niedeterministyczna maszyna Turinga | Czas poly(n) |
| NEXPTIME | Niedeterministyczna maszyna Turinga | Czas 2poly(n) |
| DSPACE(f(n)) | Deterministyczna maszyna Turinga | Miejsce f(n) |
| L | Deterministyczna maszyna Turinga | Miejsce O(log n) |
| PSPACE | Deterministyczna maszyna Turinga | Miejsce poly(n) |
| EXPSPACE | Deterministyczna maszyna Turinga | Miejsce 2poly(n) |
| NSPACE(f(n)) | Niedeterministyczna maszyna Turinga | Miejsce f(n) |
| NL | Niedeterministyczna maszyna Turinga | Miejsce O(log n) |
| NPSPACE | Niedeterministyczna maszyna Turinga | Miejsce poly(n) |
| NEXPSPACE | Niedeterministyczna maszyna Turinga | Miejsce 2poly(n) |
Z twierdzenia Savitcha wynika, że PSPACE = NPSPACE i EXPSPACE = NEXPSPACE.
Klasa NP
Do tej klasy należą wszystkie problemy decyzyjne, które rozwiązuje niedeterministyczny algorytm wielomianowy (ang. non-deterministic polynomial).
Niedeterministyczny algorytm to taki, który zawiera instrukcję: choice. Działa ona w sposób losowy, a mianowicie zwraca losowo 0 bądź 1. Tak więc można powiedzieć, że instrukcja choice odgaduje rozwiązanie. Algorytm przerywa działanie, jeżeli odgadnięte rozwiązanie będzie prawidłowe i zwraca wartość success.
Przykładem problemu klasy NP jest pytanie „czy dana liczba jest złożona”. Algorytm niedeterministyczny dla tego problemu odgaduje kolejne bity dzielnika danej liczby. Kolejnym krokiem jest sprawdzenie czy otrzymany w sposób niedeterministyczny dzielnik faktycznie dzieli daną liczbę.
Klasa Co-NP
Do tej klasy co-NP należą wszystkie problemy, których rozwiązania negatywne, razem z odpowiednim certyfikatem można potwierdzić w czasie wielomianowym.
Jeśli problem X należy do NP, to problem NIE-X należy do Co-NP.
Przykładowym problemem klasy Co-NP może być pytanie „czy dana liczba jest pierwsza”. Rozwiązanie negatywne, którego certyfikatem jest dzielnik może być łatwo sprawdzone.