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>
