Класс P — различия между версиями
Tsar (обсуждение | вклад) м (→Определение: "В перечислениях в конце каждого пункта ставится либо точка, либо точка с запятой") |
Tsar (обсуждение | вклад) (→Свойства класса P: Упихал доказательство в отдельную лемму) |
||
Строка 14: | Строка 14: | ||
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>. | # Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>. | ||
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>. | # Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>. | ||
− | # Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>. | + | # Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично). |
− | + | ||
+ | {{Лемма | ||
+ | |statement = | ||
+ | Если <tex>L \in P</tex>, то <tex>L^* \in P</tex>. | ||
+ | |proof = | ||
+ | Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>. | ||
<tex>q(w):</tex> | <tex>q(w):</tex> | ||
<tex>n = |w|</tex> | <tex>n = |w|</tex> | ||
Строка 21: | Строка 26: | ||
for (<tex>i = 1 \ldots n</tex>) | for (<tex>i = 1 \ldots n</tex>) | ||
for (<tex>j \in endPoses</tex>) | for (<tex>j \in endPoses</tex>) | ||
− | if (<tex> | + | if (<tex>p(w[j+1 \ldots i])</tex>) { |
if (<tex>i = n</tex>) | if (<tex>i = n</tex>) | ||
return true | return true | ||
Строка 27: | Строка 32: | ||
} | } | ||
return false | return false | ||
− | Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O( | + | Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in P</tex>. |
+ | }} | ||
== Соотношение классов Reg и P == | == Соотношение классов Reg и P == |
Версия 12:53, 6 мая 2012
Содержание
Определение
Определение: |
Класс [1]. | — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:
Итого, язык лежит в классе тогда и только тогда, когда существует такая детерминированная машина Тьюринга , что:
- завершает свою работу за полиномиальное время на любых входных данных;
- если на вход машине подать слово , то она допустит его;
- если на вход машине подать слово , то она не допустит его.
Свойства класса P
- Замкнутость относительно сведения по Карпу. .
- Замкнутость относительно сведения по Куку. .
- Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если , то: , , , и . Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).
Лемма: |
Если , то . |
Доказательство: |
Пусть — разрешитель , работающий за полиномиальное время. Построим разрешитель для языка .Худшая оценка времени работы разрешителя //позиции, где могут заканчиваться слова, принадлежащие for ( ) for ( ) if ( ) { if ( ) return true } return false равна , так как в множестве может быть максимум элементов, значит итерироваться по множеству можно за , если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за . Итого, разрешитель работает за полиномиальное время (так как произведение полиномов есть полином). Значит . |
Соотношение классов Reg и P
Теорема: |
Класс регулярных языков входит в класс , то есть: . |
Доказательство: |
Замечание. — ограничение и по времени и по памяти. |
Соотношение классов CFL и P
Теорема: |
Класс контекстно-свободных языков входит в класс , то есть: . |
Доказательство: |
Первое включение выполняется благодаря существованию алгоритма Эрли. |
Примеры задач и языков из P
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
- определение связности графов;
- вычисление наибольшего общего делителя;
- задача линейного программирования;
- проверка простоты числа.[2]
По теореме о временной иерархии существуют и задачи не из .
Задача равенства P и NP
Одним из центральных вопросов теории сложности является вопрос о равенстве классов NP, не разрешенный по сей день.
иЛегко показать, что, по определению
, , так как для любой задачи класса существует соответствующая ДМТ, которая является частным случаем НМТ, а значит задача, по определению, будет входить в класс .