83
правки
Изменения
Нет описания правки
В теории сложности '''Класс''' <tex>P</tex> - — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть
<tex>P=\bigcup_{i=0}^{\infty} DTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} DTIME(in^k)</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> &mdash ; множество языков, разрешимых с органичением C с помощью оракула из D (C и D — сложностные классы).
==Примеры задач и языков из <tex>P</tex>==
