Класс P

Определение

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

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

Итого, язык [math]L[/math] лежит в классе [math]P[/math] тогда и только тогда, когда существует такая детерминированная машина Тьюринга [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 \in P , M \le L \Rightarrow M \in P[/math].
2. Замкнутость относительно сведения по Куку. [math]L \subset P \Rightarrow P=P^L[/math].
3. Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если [math]L_1, L_2 \in P[/math], то: [math]L_1 \cup L_2 \in P[/math], [math]L_1 \cap L_2 \in P[/math], [math]L_1 L_2 \in P[/math], [math]L_1^* \in P[/math] и [math]\overline{L_1} \in P[/math]. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).

Лемма:

Если [math]L \in P[/math], то [math]L^* \in P[/math].

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

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

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

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

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

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