Igor в 21:34, 10 декабря 2016

2016-12-10T21:34:53Z

Igor: Новая страница: « Для пары G, H выполним следующий алгоритм: \begin{itemize} \item{Если в G и H разное количество ве…»

2016-12-10T21:30:43Z

Новая страница: «<latex> Для пары G, H выполним следующий алгоритм: \begin{itemize} \item{Если в G и H разное количество ве…»

Новая страница

<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>

[[Категория:Предложенные студентами задачи]]

← Предыдущая		Версия 21:34, 10 декабря 2016
Строка 9:		Строка 9:
	Ясно, что шаги 1 и 3 можно выполнить за полиномиальное время, а второй шаг - за полиномиальное время недетерминированно. Следовательно, $ISO\in NP$.		Ясно, что шаги 1 и 3 можно выполнить за полиномиальное время, а второй шаг - за полиномиальное время недетерминированно. Следовательно, $ISO\in NP$.
	</latex>		</latex>
−
−	~~[[Категория:Предложенные студентами задачи]]~~

ISO in NP/Решение Иноземцев - История изменений

Igor в 21:34, 10 декабря 2016

Igor: Новая страница: « Для пары G, H выполним следующий алгоритм: \begin{itemize} \item{Если в G и H разное количество ве…»