#* Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично). Пусть <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 (<tex>n = |w| </tex> <tex>endPoses = \{0) return true\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L_1</tex> for (<tex>i = 1 \ldots |w|n</tex>) for (<tex>j \in endPoses</tex>) if (<tex>p_1(w[j+1..\ldots i])</tex> and ) { if (<tex>q(w[i + 1..|w|])= n</tex>) return true <tex>endPoses</tex> <tex>\cup = \{i\}</tex> }
return false
Мне кажетсяХудшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p_1(w))</tex>, он так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов. Итого, разрешитель <tex>q</tex> работает за полином работаетполиномиальное время. Завтра формально напишу, почему (если смогу)Значит <tex>L_1^* \in P</tex>.
== Соотношение классов Reg и P ==
