Класс P

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

Определение

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

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

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

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

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

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

• нахождение делителей числа (язык делителей числа)
• поиск диаметра связного графа

Но существуют и задачи не из P, по теореме о временной иерархии, существуют задачи, работающие за более чем [math]p(x) \in Poly[/math], а значит не входящие в объединение [math]\bigcup_{i=0}^{\infty} DTIME(in^i)[/math], что и требовалось показать.

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

Основополагающей задачей теории сложности является задача равенства классов P и NP, не разрешенная по сей день. Однако легко показать, что по определению, [math] P \subset NP[/math], так как достаточно для любой задачи класса P привести ее решение в качестве сертификата, а значит задача по определению будет входить в класс NP