ISO in NP/Решение Иноземцев — различия между версиями
Материал из DISCOPAL
Igor (обсуждение | вклад) (Новая страница: «<latex> Для пары G, H выполним следующий алгоритм: \begin{itemize} \item{Если в G и H разное количество ве…») |
Igor (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
Ясно, что шаги 1 и 3 можно выполнить за полиномиальное время, а второй шаг - за полиномиальное время недетерминированно. Следовательно, $ISO\in NP$. | Ясно, что шаги 1 и 3 можно выполнить за полиномиальное время, а второй шаг - за полиномиальное время недетерминированно. Следовательно, $ISO\in NP$. | ||
</latex> | </latex> | ||
| − | |||
| − | |||
Текущая версия на 21:34, 10 декабря 2016