Wymaga to tylko wielomianowo wiele kroków, ponieważ wybór kolejnego znaku świadka odbywa się w sposób niedeterministyczny, a długość świadka musi być ograniczona z góry przez wielomian względem długości słowa wejściowego. Jeśli dla danego słowa wejściowego istnieje jakikolwiek poprawny świadek, będzie również istniał akceptujący przebieg niedeterministycznej maszyny. Natomiast jeśli świadek nie istnieje, to znaczy, że wszystkie przebiegi maszyny odrzucą słowo wejściowe. Z poprawności weryfikatora wiemy jednak, że słowo takie nie należy do rozważanego języka.
Z drugiej strony, przypuśćmy, że mamy daną niedeterministyczną maszynę Turinga akceptującą język w czasie wielomianowym. W każdym z wielomianowo wielu kroków drzewo obliczeń maszyny może rozgałęziać się na co najwyżej skończoną liczbę różnych przebiegów. Dla danego słowa wejściowego możemy zatem zakodować przebiegi maszyny przy użyciu słów o długości ograniczonej wielomianem względem długości wejścia. Weryfikator może zatem dla podanej na wejściu pary (, ) symulować przebieg maszyny na słowie wejściowym . Jeśli każdy przebieg maszyny odrzucał , nie będzie istniał poprawny świadek. Jeśli natomiast maszyna akceptowała to słowo w pewnym przebiegu, to jego kodowanie będzie poprawnym świadkiem.
Powiązania z innymi klasami złożoności
Fakt ten wynika wprost z faktu, że deterministyczna maszyna Turinga jest szczególnym przypadkiem maszyny niedeterministycznej