Wprowadzenie Wiele naturalnych problemów algorytmicznych znajduje się w klasie złożoności NP. W szczególności, decyzyjne wersje wielu interesujących problemów przeszukiwania oraz problemów optymalizacyjnych należą do NP.
Definicja bazująca na weryfikatorach W celu wyjaśnienia definicji klasy NP bazującej na weryfikatorach przeanalizujemy problem sumy podzbioru:
Mając dany skończony zbiór składający się wyłącznie z liczb całkowitych (na przykład {−7, −3, −2, 5, 8}), rozstrzygnąć, czy istnieje taki jego niepusty podzbiór, którego elementy sumują się do zera (w naszym przykładzie odpowiedź jest pozytywna, gdyż podzbiorowi {-3, -2, 5} odpowiada suma ).
Moglibyśmy zaproponować algorytm rozwiązujący powyższy problem, a bazujący na sprawdzaniu wszystkich możliwych podzbiorów. Niestety, liczba podzbiorów, a tym samym czas obliczeń, rośnie wykładniczo w stosunku do rozmiaru podanego zbioru. Zauważmy jednak, że mając podany pewien podzbiór, możemy łatwo sprawdzić, czy suma jego elementów wynosi zero. Jeśli tak jest, mówimy, że dany zbiór jest świadkiem faktu, że odpowiedź na zadany problem jest pozytywna. Algorytm sprawdzający, czy elementy zadanego zbioru sumują się do zera, nazywamy natomiast weryfikatorem.