141
правка
Изменения
м
Может это моё личное мнение, но заголовки с tex-ом выглядят ужасно, к тому же из содержания tex-овские куски выпадают
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его
== Свойства класса <tex>P</tex> ==
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L1 \cup L2 \in P</tex>, <tex>L1 \cap L2 \in P</tex>, <tex>L1L2 \in P</tex>, <tex>L1^* \in P</tex> и <tex>\overline{L1} \in P</tex>.
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.
== Соотношение классов <tex>Reg</tex> и <tex>P</tex> ==
{{Теорема
|statement =
}}
== Соотношение классов <tex>CFL</tex> и <tex>P</tex> ==
{{Теорема
|statement =
}}
== Примеры задач и языков из <tex>P</tex> ==
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
* определение связности графов;
Но, по [[теорема о временной иерархии|теореме о временной иерархии]] существуют и задачи не из <tex>P</tex>.
== Задача равенства <tex>P</tex> и <tex>NP</tex> ==
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и [[NP]], не разрешенный по сей день.
