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:

Więcej informacji Model obliczeń, Ograniczenie zasobów ...
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)
Zamknij

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.

Zobacz też

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.