Класс P

2012-06-03T07:46:24Z

178.162.101.7: /* Свойства класса P */ s/очевидно/понятно/

== Определение ==
{{Определение
|definition=
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:
<tex>\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.
}}

Итого, язык <tex>L</tex> лежит в классе <tex>\mathrm{P}</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.

== Свойства класса P ==
{{Лемма
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \in \mathrm{P}</tex>.
|proof =
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время.
<tex> (M \leq L) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \mathrm{\widetilde{P}} : w \in M \Leftrightarrow f(w) \in L ) </tex>.
Построим разрешитель <tex>q</tex> для языка <tex>M</tex>.
<tex>q(w):</tex>
if (<tex>p(f(w))</tex>)
return true
return false
Разрешитель <tex>q</tex> работает за полиномиальное время, так как композиция полиномов есть полином.
}}

{{Лемма
|statement =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <tex>\mathrm{P} \subset \mathrm{P}^D</tex>. Докажем, что <tex>\mathrm{P}^D \subset \mathrm{P}</tex>.

<tex>L \in \mathrm{P}^D \Rightarrow \exists A \in D: L \in \mathrm{P}^A</tex>.

Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время <tex>f(n)</tex> и использующий оракул языка <tex>A</tex>.
Пусть <tex>q</tex> {{---}} разрешитель <tex>A</tex>, работающий за полиномиальное время <tex>g(n)</tex>.
Представим себе разрешитель <tex>L</tex>, работающий как <tex>p</tex>, но использующий <tex>q</tex> вместо оракула <tex>A</tex>. Его время работы ограничено сверху значением <tex>f(n) + \sum\limits_{i=1}^{f(n)} g(f(n)) = f(n) + f(n) g(f(n))</tex>, что является полиномом (обращений к <tex>q</tex> максимум <tex>f(n)</tex>; на вход для <tex>q</tex> можем подать максимум <tex>f(n)</tex> данных, так как больше сгенерить бы не успели). Значит, <tex>L \in \mathrm{P}</tex>.
}}

{{Лемма
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно операций объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in \mathrm{P}</tex>, то: <tex>L_1 \cup L_2 \in \mathrm{P}</tex>, <tex>L_1 \cap L_2 \in \mathrm{P}</tex>, <tex>L_1 L_2 \in \mathrm{P}</tex>, <tex>L_1^* \in \mathrm{P}</tex> и <tex>\overline{L_1} \in \mathrm{P}</tex>.
|proof =
Докажем замкнутость замыкания Клини. Остальные доказательства строятся аналогично.

Пусть <tex>p</tex> {{---}} разрешитель <tex>L_1</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L_1</tex>
for (<tex>i = 1 \ldots n</tex>)
for (<tex>j \in endPoses</tex>)
if (<tex>p(w[j+1 \ldots i])</tex>) {
if (<tex>i = n</tex>)
return true
<tex>endPoses</tex> <tex>\cup = \{i\}</tex>
}
return false
Худшая оценка времени работы разрешителя <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_1^* \in \mathrm{P}</tex>.
}}

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
''Замечание.'' <tex>\mathrm{TS}</tex> {{---}} ограничение и по времени, и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из P ==
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
* определение связности графов;
* вычисление наибольшего общего делителя;
* задача линейного программирования;
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref>

По [[теорема о временной иерархии|теореме о временной иерархии]] существуют задачи и не из <tex>\mathrm{P}</tex>.

== Ссылки ==
<references/>

[[Категория: Теория сложности]]

Викиконспекты - Вклад участника [ru]

Класс P