Jeśli A \subseteq N^2 należy do P, to istnieje maszyna Turinga M_A i wielomian p takie, że M_A rozpoznaje czy n \in A po nie więcej niż p(|n|) krokach.
Rozważmy zbiór \Pi=\{n:\exists m. |m|\leq p(|n|) \wedge (n,m)\in A \}.
Skonstruujmy niedeterministyczną maszynę Turinga M_{\Pi}, która najpierw wyznacza blok o długości p(|n|) (za obecną zawartością taśmy), niedeterministycznie zapisuje go zerami i jedynkami, a potem zachowuje się jak M_A, gdzie niedeterministycznie zgadnięta liczba to m.
M_{\Pi} rozpoznaje \Pi, więc \Pi jest w NP.