141
правка
Изменения
→Свойства класса P
== Свойства класса P ==
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>.
#* Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично). Пусть <tex>L_1 \in P</tex>, <tex>p_1</tex> {{---}} разрешитель <tex>L_1</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L_1^*</tex>.
<tex>q(w):</tex>
if (|w| = 0)
return true
for (<tex>i = 1 \ldots |w|</tex>)
if (<tex>p_1(w[1..i])</tex> and <tex>q(w[i + 1..|w|])</tex>)
return true
return false
Мне кажется, он за полином работает. Завтра формально напишу, почему (если смогу).
== Соотношение классов Reg и P ==
