141
правка
Изменения
м
→Примеры задач и языков из P: Союз "и" нелеп
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref>
Но существуют задачи и не из <tex>\mathrm{P}</tex>, так как из [[теорема о временной иерархии|теоремы о временной иерархии]] следует, что <tex>\exists L \in \mathrm{EXP}\setminus\mathrm{P}</tex>.
