ISO in NP/Решение Иноземцев — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<latex> Для пары G, H выполним следующий алгоритм: \begin{itemize} \item{Если в G и H разное количество ве…»)
 
 
Строка 9: Строка 9:
 
Ясно, что шаги 1 и 3 можно выполнить за полиномиальное время, а второй шаг - за полиномиальное время недетерминированно. Следовательно, $ISO\in NP$.
 
Ясно, что шаги 1 и 3 можно выполнить за полиномиальное время, а второй шаг - за полиномиальное время недетерминированно. Следовательно, $ISO\in NP$.
 
</latex>
 
</latex>
 
[[Категория:Предложенные студентами задачи]]
 

Текущая версия на 00:34, 11 декабря 2016