Класс P

Определение

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

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

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

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

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

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

$q(w):$
    $n = |w|$
    $endPoses = \{0\}$  //позиции, где могут заканчиваться слова, принадлежащие $L_1$
    for ($i = 1 \ldots n$)
        for ($j \in endPoses$)
            if ($p_1(w[j+1 \ldots i])$) {
                if ($i = n$)
                    return true
                $endPoses$ $\cup = \{i\}$
            }
    return false

Худшая оценка времени работы разрешителя $q$ равна $n^2 O(p_1(w))$, так как в множестве $endPoses$ может быть максимум $n$ элементов, значит итерироваться по множеству можно за $n$, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за $O(1)$. Итого, разрешитель $q$ работает за полиномиальное время (так как произведение полиномов есть полином). Значит $L_1^* \in P$.

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

Теорема:

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

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

$\triangleright$

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

$\triangleleft$

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

Теорема:

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

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

$\triangleright$

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

$\triangleleft$

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

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

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

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

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

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

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