Изменения
→Свойства класса P
== Свойства класса P ==
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in \mathrm{P } , M \le L \Rightarrow M \in \mathrm{P}</tex>.# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>\mathrm{L } \subset \mathrm{P } \Rightarrow \mathrm{P}=\mathrm{P^L}</tex>.# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in \mathrm{P}</tex>, то: <tex>L_1 \cup L_2 \in \mathrm{P}</tex>, <tex>L_1 \cap L_2 \in \mathrm{P}</tex>, <tex>L_1 L_2 \in \mathrm{P}</tex>, <tex>L_1^* \in \mathrm{P}</tex> и <tex>\overline{L_1} \in \mathrm{P}</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).
{{Лемма
|statement =
Если <tex>L \in \mathrm{P}</tex>, то <tex>L^* \in \mathrm{P}</tex>.
|proof =
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L_1L</tex>
for (<tex>i = 1 \ldots n</tex>)
for (<tex>j \in endPoses</tex>)
}
return false
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in \mathrm{P}</tex>.
}}
