W związku z tym, oraz z powodu wielu przeprowadzonych badań skupiających się na znalezieniu wielomianowych rozwiązań dla problemów NP-zupełnych, które zakończyły się niepowodzeniem, jeśli dla danego problemu zostanie udowodnione, że jest on NP-zupełny, to jest wielce prawdopodobne, że nie istnieje dla niego algorytm wielomianowy.
Tym niemniej, dla niektórych problemów NP istnieją algorytmy wielomianowe, które dają rozwiązanie nieoptymalne, ale często wystarczająco dobre. Ponadto rzeczywiste przypadki niektórych problemów są łatwiejsze do rozwiązania niż ich teoretyczne odpowiedniki.
Równoważność definicji Obie definicje klasy złożoności obliczeniowej NP – ta przedstawiająca ją jako zbiór języków akceptowanych przez niedeterministyczne maszyny Turinga w czasie wielomianowej, oraz ta mówiąca, że są to problemy o rozwiązaniach weryfikowalnych przez deterministyczną maszynę Turinga – są sobie równoważne.
W celu udowodnienia tego faktu przyjmijmy najpierw, że mamy deterministyczny weryfikator. Niedeterministyczna maszyna Turinga może w prosty sposób zasymulować działanie tego weryfikatora na słowie wejściowym oraz wszystkich możliwych świadkach.