Klasa złożoności

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.