83
правки
Изменения
Нет описания правки
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Карпу|сведения по Куку]]. <tex> L \in P , M {\le}_c L \Rightarrow M \in P</tex>
# <tex>L \subset P \Rightarrow P=P^L</tex>, где <tex>C^D</tex> &mdash
==Примеры задач и языков из <tex>P</tex>==
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
*определение связности графов;* вычисление наибольшего общего делителя;* проверка простоты числа.
Но, по [[теорема о временной иерархии|теореме о временной иерархии]] существуют и задачи не из <tex>P</tex>.
