141
правка
Изменения
Попытки что-то исправить (пункты от АС №3, 4, 5)
== Свойства класса P ==
{{ЛеммаТеорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \in \mathrm{P}</tex>.
{{ЛеммаТеорема
|statement =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
{{ЛеммаТеорема
|statement =
Класс <tex>\mathrm{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>.
}}
== Соотношение классов Reg Примеры задач и языков из P ==Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:* определение связности графов;* вычисление наибольшего общего делителя;* задача линейного программирования;* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref> Но существуют задачи и не из <tex>\mathrm{P}</tex>, так как из [[теорема о временной иерархии|теореме о временной иерархии]] следует, что <tex>\exists L \in \mathrm{EXP}\setminus\mathrm{P}</tex>.
{{Теорема
|statement =
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}
{{Теорема
|statement =
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}
== Ссылки ==
