Класс P

Определение

Определение:

Класс $\mathrm{P}$ — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть: $\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))$.

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

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

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

1. Замкнутость относительно сведения по Карпу. $L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}$.
2. Замкнутость относительно сведения по Куку. $\mathrm{L} \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P^L}$.
3. Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если $L_1, L_2 \in \mathrm{P}$, то: $L_1 \cup L_2 \in \mathrm{P}$, $L_1 \cap L_2 \in \mathrm{P}$, $L_1 L_2 \in \mathrm{P}$, $L_1^* \in \mathrm{P}$ и $\overline{L_1} \in \mathrm{P}$. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).

Лемма:

Если $L \in \mathrm{P}$, то $L^* \in \mathrm{P}$.

Доказательство:

$\triangleright$

Пусть $p$ — разрешитель $L$, работающий за полиномиальное время. Построим разрешитель $q$ для языка $L^*$. $q(w):$ $n = |w|$ $endPoses = \{0\}$ //позиции, где могут заканчиваться слова, принадлежащие $L$ for ($i = 1 \ldots n$) for ($j \in endPoses$) if ($p(w[j+1 \ldots i])$) { if ($i = n$) return true $endPoses$ $\cup = \{i\}$ } return false Худшая оценка времени работы разрешителя $q$ равна $n^2 O(p(w))$, так как в множестве $endPoses$ может быть максимум $n$ элементов, значит итерироваться по множеству можно за $n$, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за $O(1)$. Итого, разрешитель $q$ работает за полиномиальное время (так как произведение полиномов есть полином). Значит $L^* \in \mathrm{P}$.

$\triangleleft$

Соотношение классов Reg и P

Теорема:

Класс регулярных языков входит в класс $\mathrm{P}$, то есть: $\mathrm{Reg} \subset \mathrm{P}$.

Доказательство:

$\triangleright$

$\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}$ Замечание. $\mathrm{TS}$ — ограничение и по времени, и по памяти.

$\triangleleft$

Соотношение классов CFL и P

Теорема:

Класс контекстно-свободных языков входит в класс $\mathrm{P}$, то есть: $\mathrm{CFL} \subset P$.

Доказательство:

$\triangleright$

$\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}$ Первое включение выполняется благодаря существованию алгоритма Эрли.

$\triangleleft$

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

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

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

По теореме о временной иерархии существуют задачи и не из $\mathrm{P}$.

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

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

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