Изменения

В теории сложности '''Класс P''' <tex>P</tex> - класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть  <tex>P=\bigcup_{i=0}^{\infty} DTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} DTIME(in^k)</tex>.

Язык L лежит в классе '''<tex>P''' </tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга ''<tex>m''</tex>, что:# ''<tex>m'' </tex> завершает свою работу за полиномиальное время на любых входных данных # если на вход машине ''<tex>m'' </tex> подать слово <tex>l \in L</tex>, то она допустит его# если на вход машине ''<tex>m'' </tex> подать слово <tex>l \not\in L</tex>, то она не допустит его

==Свойства класса '''<tex>P'''</tex>==

# Замкнутость относительно [[сведения по Карпу|Сведение по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex># Замкнутость относительно [[сведения по Куку|Сведение по Куку]]. <tex> L \in P , M {\le}_c L \Rightarrow M \in P</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>