Bardziej ogólnie, mówimy, że problem obliczeniowy należy do NP, jeśli istnieje dla niego weryfikator . Mając dowolny egzemplarz problemu , dla którego odpowiedź jest pozytywna, musi istnieć świadek , taki że akceptuje słowo wejściowe (, ) w czasie wielomianowym. Co więcej, jeśli odpowiedź na jest negatywna, weryfikator odrzuci słowo (, ) dla wszystkich możliwych . Zauważ, że weryfikator może odrzucić wejście nawet, gdy odpowiedź jest pozytywna, jeśli tylko nie jest poprawnym świadkiem. Dla przykładu, w przypadku problemu sumy podzbioru, jeśli istnieje podzbiór, którego elementy sumują się do zera, ale jako świadek wybrany zostanie inny podzbiór, dla którego nie jest to prawdą, weryfikator odrzuci słowo wejściowe. Jeśli jednak nie istnieje podzbiór o zerowej sumie, weryfikator będzie odrzucał wejście niezależnie od wyboru świadka. Ponadto w przypadku tego problemu, weryfikator działa w czasie wielomianowym (potrzeba jedynie sprawdzić, czy faktycznie jest podzbiorem oraz czy suma jego elementów jest zerowa), a zatem problem sumy podzbioru należy do klasy NP.