Изменения

Перейти к: навигация, поиск

Класс P

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

Навигация