Klasa złożoności – Wikipedia, wolna encyklopedia

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 ${\displaystyle (n^{O(1)}),}$ 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 ${\displaystyle (\log ^{O(1)}n)}$ 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”

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:

Z twierdzenia Savitcha wynika, że PSPACE = NPSPACE i EXPSPACE = NEXPSPACE.

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ę.

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.

• teoria obliczalności