===== JFiZO - Zadanie 86 =====
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$.

  * $M_{\Pi}$ =
    * read n
    * guess m
    * run $M_a(n,m)$
    * accept if $M_a$ accepts, reject otherwise