53
правки
Изменения
Нет описания правки
# Замкнутость относительно дополнений. <tex> L \in P \Rightarrow \overline L \in P</tex>
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <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> — множество языков, разрешимых с органичением C с помощью оракула из D (C и D — сложностные классы).
==Примеры задач и языков из <tex>P</tex>==
