83
правки
Изменения
Нет описания правки
* определение связности графов;
* вычисление наибольшего общего делителя.
* проверка простоты числа.<ref>M.Argawal, N.Kayal, N.Saxena, "Primes is in P"</ref>
Но, по [[теорема о временной иерархии|теореме о временной иерархии]] существуют и задачи не из <tex>P</tex>.
Легко показать, что по определению, <tex> P \subset NP</tex>, так как достаточно для любой задачи класса <tex>P</tex> существует соответствующая ДМТ, которая является частным случаем НМТ, а значит задача по определению будет входить в класс <tex>NP</tex>
==Ссылки==
<references/>
