Изменения

В теории сложности '''КлассP''' <tex>P</tex> &mdash; класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть

'''P'''=<tex>P=\bigcup_{i=0}^{\infty} </tex>'''[[DTIME]]'''<tex>(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} </tex>'''DTIME'''<tex>(in^k)</tex>.

Язык L лежит в классе <tex>PL</tex> лежит в классе '''P''' тогда и только тогда, когда существует такая детерминированная машина Тьюринга <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 </tex> ∈ '''P ''' <tex>\Rightarrow \overline L \in P</tex>∈ '''P'''# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in </tex> ∈ '''P ''' , <tex>M \le L \Rightarrow M \in P</tex>∈ '''P'''# Замкнутость относительно [[Сведение по Карпу|сведения по Куку]]. <tex>L \subset </tex> ⊂ '''P ''' <tex>\Rightarrow </tex> '''P'''='''P^'''^{<math>L</texmath>}.

==Примеры задач и языков из <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>'''.