Просмотр исходного текста страницы ISO in NP/Решение Иноземцев

<latex>
Для пары G, H выполним следующий алгоритм:
\begin{itemize}
\item{Если в G и H разное количество вершин, отвергаем эту пару}
\item{Недетерминированно получаем какую-либо перестановку ($\pi$) n элементов (n - количество вершин в G)}
\item{Для каждой пары (x, y) проверяем, что в графе G есть ребро между x и y тогда и только тогда, когда в графе H есть ребро между $\pi(x)$ и $\pi(y)$.}
\end{itemize}

Ясно, что шаги 1 и 3 можно выполнить за полиномиальное время, а второй шаг - за полиномиальное время недетерминированно. Следовательно, $ISO\in NP$.
</latex>