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ż teoria obliczalności