Класс P — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства класса P: Разбиение свойств на 3 леммы, первые 2 ещё без доказательств)
(Свойства класса P: Тривиальное доказательство первого свойства)
Строка 14: Строка 14:
 
{{Лемма
 
{{Лемма
 
|statement =
 
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex> L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}</tex>.
+
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \in \mathrm{P}</tex>.
 
|proof =
 
|proof =
...появится с минуты на минуту...
+
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время.
 +
<tex> (M \leq L) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \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> работает за полиномиальное время, так как композиция полиномов есть полином.
 
}}
 
}}
  

Версия 18:57, 2 июня 2012

Определение

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


Итого, язык [math]L[/math] лежит в классе [math]\mathrm{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

Лемма:
Класс [math]\mathrm{P}[/math] замкнут относительно сведения по Карпу. [math]L \in \mathrm{P}, M \le L \Rightarrow M \in \mathrm{P}[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]p[/math] — разрешитель [math]L[/math], работающий за полиномиальное время. [math] (M \leq L) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \widetilde{P} : w \in M \Leftrightarrow f(w) \in L ) [/math]. Построим разрешитель [math]q[/math] для языка [math]M[/math].

[math]q(w):[/math]
    if ([math]p(f(w))[/math])
        return true
    return false
Разрешитель [math]q[/math] работает за полиномиальное время, так как композиция полиномов есть полином.
[math]\triangleleft[/math]


Лемма:
[math]L \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^L[/math]. В частности, из этого следует, что [math]\mathrm{P}=\mathrm{P^P}[/math].
Доказательство:
[math]\triangleright[/math]
...появится с минуты на минуту...
[math]\triangleleft[/math]


Лемма:
Класс [math]\mathrm{P}[/math] замкнут относительно операций объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если [math]L_1, L_2 \in \mathrm{P}[/math], то: [math]L_1 \cup L_2 \in \mathrm{P}[/math], [math]L_1 \cap L_2 \in \mathrm{P}[/math], [math]L_1 L_2 \in \mathrm{P}[/math], [math]L_1^* \in \mathrm{P}[/math] и [math]\overline{L_1} \in \mathrm{P}[/math].
Доказательство:
[math]\triangleright[/math]

Докажем замкнутость замыкания Клини. Остальные доказательства строятся аналогично.

Пусть [math]p[/math] — разрешитель [math]L_1[/math], работающий за полиномиальное время. Построим разрешитель [math]q[/math] для языка [math]L_1^*[/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_1^* \in \mathrm{P}[/math].
[math]\triangleleft[/math]

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

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

[math]\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}[/math]

Замечание. [math]\mathrm{TS}[/math] — ограничение и по времени, и по памяти.
[math]\triangleleft[/math]

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

Теорема:
Класс контекстно-свободных языков входит в класс [math]\mathrm{P}[/math], то есть: [math]\mathrm{CFL} \subset P[/math].
Доказательство:
[math]\triangleright[/math]

[math]\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}[/math]

Первое включение выполняется благодаря существованию алгоритма Эрли.
[math]\triangleleft[/math]

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

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

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


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

Ссылки