Изменения

# Замкнутость {{Лемма|statement =Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex> L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}</tex>.# |proof =...появится с минуты на минуту...}}  {{Лемма|statement =<tex>L \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^L</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения|proof =.. Если <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>.Первые два свойства следуют из определений сведения по Карпу и вычислений появится с оракулом соответственноминуты на минуту...<br/>Так как доказательства пунктов третьего свойства аналогичны, рассмотрим, для примера, доказательство замкнутости замыкания Клини.}} 

Класс <tex>\mathrm{P}</tex> замкнут относительно операций объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L 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>LL_1^* \in \mathrm{P}</tex> и <tex>\overline{L_1} \in \mathrm{P}</tex>.

Докажем замкнутость замыкания Клини. Остальные доказательства строятся аналогично. Пусть <tex>p</tex> {{---}} разрешитель <tex>LL_1</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>LL_1^*</tex>.

<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>LL_1</tex>

Худшая оценка времени работы разрешителя <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>LL_1^* \in \mathrm{P}</tex>.