Z drugiej strony, jeśli istnieje niedeterministyczna maszyna rozwiązująca pewien problem z NP, możemy łatwo skonstruować weryfikator dla tego problemu. Będzie on w deterministyczny sposób symulował pewien przebieg maszyny , korzystając ze świadka za każdym razem, gdy należy dokonać niedeterministycznego wyboru.
Przykłady Poniżej znajduje się niekompletna lista problemów znajdujących się w klasie NP.
Wszystkie problemy z klasy P (Dla dowolnego świadka weryfikator może go zignorować i rozwiązać problem w czasie wielomianowym. Alternatywnie, deterministyczna maszyna Turinga jest jednocześnie przypadkiem szczególnym maszyny niedeterministycznej.) Wersja decyzyjna problemu faktoryzacji: mając dane liczby naturalne oraz , rozstrzygnąć, czy istnieje dzielnik liczby , taki że 1 < < . Problem izomorfizmu grafów. Wszystkie problemy NP-zupełne, między innymi: Problem komiwojażera, polegający na znalezieniu cyklu o minimalnej sumie wag, zawierającego wszystkie wierzchołki grafu Problem spełnialności: mając daną formułę logiczną, rozstrzygnąć, czy istnieje takie wartościowanie zmiennych zdaniowych, żeby formuła była prawdziwa.
Własności Klasa NP jest zamknięta na: sumę zbiorów przecięcie zbiorów konkatenację domknięcie Kleene’ego odwrotność