Klasa złożoności

W teorii obliczeń klasa złożoności to 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 ($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 ($\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"

Ważne klasy złożoności

Wiele ważnych klas złożoności można zdefiniować przez ograniczenie czasu lub miejsca zużytego przez 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 (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ład problemu klasy NP

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 podzielnik faktycznie dzieli daną liczbę.

Klasa Co-NP

Do tej klasy 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ład problemu klasy 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.