Klasa złożoności

Z Wikipedii

Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi.
Należy w nim poprawić: uspójnić, ułożyć, dodać przykłady.
Po naprawieniu wszystkich błędów można usunąć tę wiadomość.

W teorii obliczeń klasa złożoności to zbiór problemów obliczeniowych o podobnej złożoności obliczeniowej. Zwykle klasa złożoności ma definicję następującej postaci:

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.

[edytuj] NP, Co-NP

Klasa NP to 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ł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 to 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. Tak więc 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.