141
правка
Изменения
+ теоремка
'''Класс''' <tex>P</tex> — {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть
<tex>P=\bigcup\limits_{i=0}^{\infty} DTIME(in^i)=\bigcup\limits_{i=0}^{\infty}\bigcup\limits_{k=0}^{\infty} DTIME(in^k)</tex>.
==Определение==
Язык L лежит в классе <tex>P</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:
# <tex>m</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>Reg \subset P</tex>|proof =<tex>Reg \subset TS(n, 1) \subset P</tex>''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.}}
==Примеры задач и языков из <tex>P</tex>==
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
* определение связности графов;
Но, по [[теорема о временной иерархии|теореме о временной иерархии]] существуют и задачи не из <tex>P</tex>.
==Задача равенства <tex>P</tex> и <tex>NP</tex>==
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и [[NP]], не разрешенный по сей день.
Легко показать, что, по определению, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая ДМТ, которая является частным случаем НМТ, а значит задача, по определению, будет входить в класс <tex>NP</tex>.
==Ссылки==
<references/>
