Класс P

В теории сложности Класс P — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть

P=[math]\bigcup_{i=0}^{\infty}[/math]DTIME[math](in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty}[/math]DTIME[math](in^k)[/math].

Определение

Язык [math]L[/math] лежит в классе P тогда и только тогда, когда существует такая детерминированная машина Тьюринга [math]m[/math], что:

1. [math]m[/math] завершает свою работу за полиномиальное время на любых входных данных;
2. если на вход машине [math]m[/math] подать слово [math]l \in L[/math], то она допустит его;
3. если на вход машине [math]m[/math] подать слово [math]l \not\in L[/math], то она не допустит его.

Свойства класса P

1. Замкнутость относительно дополнений. [math] L [/math] ∈ P [math]\Rightarrow \overline L [/math] ∈ P
2. Замкнутость относительно сведения по Карпу. [math]L[/math] ∈ P , [math]M \le L \Rightarrow M[/math] ∈ P
3. Замкнутость относительно сведения по Куку. [math]L[/math] ⊂ P [math]\Rightarrow[/math] P=P^{[math]L[/math]}.

Примеры задач и языков из P

Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:

• определение связности графов;
• вычисление наибольшего общего делителя.
• проверка простоты числа.

Но, по теореме о временной иерархии существуют и задачи не из P.

Задача равенства классов P и NP

Одним из центральных вопросов теории сложности является вопрос о равенстве классов P и NP, не разрешенный по сей день.

Легко показать, что, по определению, P ⊂ NP, так как для любой задачи класса P существует соответствующая ДМТ, которая является частным случаем НМТ, а значит задача, по определению, будет входить в класс NP.