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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример P-полной задачи: Определение P-полноты, всё же)
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 3 участников)
Строка 10: Строка 10:
 
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;
 
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;
 
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.
 
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.
 +
 +
== Устойчивость класса P к изменению модели вычислений ==
 +
Машина Тьюринга может симулировать другие модели вычислений (например, языки программирования) с не более чем полиномиальным замедлением. Благодаря этому, класс <tex>\mathrm{P}</tex> на этих моделях не становится шире.
 +
 +
Согласно [http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%B7%D0%B8%D1%81_%D0%A7%D1%91%D1%80%D1%87%D0%B0_%E2%80%94_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 тезису Чёрча-Тьюринга], любой физически реализуемый алгоритм можно реализовать на машине Тьюринга. Так что класс <tex>\mathrm{P}</tex> устойчив и в обратном преобразовании модели вычислений.
  
 
== Свойства класса P ==
 
== Свойства класса P ==
Строка 89: Строка 94:
  
 
== P-полные задачи ==
 
== P-полные задачи ==
{{Определение
+
Говоря про <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полноту]], мы, как правило, подразумеваем <tex>\mathrm{P}</tex>-полноту относительно <tex>\widetilde{\mathrm{L}}</tex>-сведения.<ref>[[Классы L, NL, coNL. NL-полнота задачи о достижимости]]</ref>
|definition=
 
Язык <tex>X</tex> является <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полным]], если:
 
# <tex>X \in \mathrm{P}</tex>;
 
# <tex>\forall Y \in \mathrm{P} \Rightarrow Y \leq_L X</tex> (то есть любой язык из класса <tex>\mathrm{P}</tex> сводится к <tex>X</tex> с использованием <tex>O(log(n))</tex> памяти).
 
}}
 
  
 
{{Определение
 
{{Определение
Строка 103: Строка 103:
 
{{Теорема
 
{{Теорема
 
|statement =
 
|statement =
<tex>CIRCVAL</tex> {{---}} <tex>\mathrm{P}</tex>-полная задача.
+
<tex>CIRCVAL</tex> {{---}} <tex>\mathrm{P}</tex>-полная задача.<ref>[http://www.math.sc.edu/~cooper/math778C/abct.pdf S.Arora, B.Barak, "Computational Complexity: A Modern Approach"]</ref>
 
}}
 
}}
  
Строка 109: Строка 109:
 
<references/>
 
<references/>
  
[[Категория: Теория сложности]]
+
[[Категория: Классы сложности]]

Текущая версия на 19:18, 4 сентября 2022

Определение

Определение:
Класс [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]\mathrm{P}[/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 \mathrm{\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]D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D[/math]. В частности, из этого следует, что [math]\mathrm{P}=\mathrm{P^P}[/math].
Доказательство:
[math]\triangleright[/math]

Понятно, что [math]\mathrm{P} \subset \mathrm{P}^D[/math]. Докажем, что [math]\mathrm{P}^D \subset \mathrm{P}[/math].

[math]L \in \mathrm{P}^D \Rightarrow \exists A \in D: L \in \mathrm{P}^A[/math].

Пусть [math]p[/math] — разрешитель [math]L[/math], работающий за полиномиальное время [math]f(n)[/math] и использующий оракул языка [math]A[/math]. Пусть [math]q[/math] — разрешитель [math]A[/math], работающий за полиномиальное время [math]g(n)[/math].

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

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

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

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

Но существуют задачи не из [math]\mathrm{P}[/math], так как из теоремы о временной иерархии следует, что [math]\exists L \in \mathrm{EXP}\setminus\mathrm{P}[/math].


Теорема:
Класс регулярных языков входит в класс [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]\triangleleft[/math]


Теорема:
Класс контекстно-свободных языков входит в класс [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-полные задачи

Говоря про [math]\mathrm{P}[/math]-полноту, мы, как правило, подразумеваем [math]\mathrm{P}[/math]-полноту относительно [math]\widetilde{\mathrm{L}}[/math]-сведения.[3]


Определение:
[math]CIRCVAL = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}[/math], где [math]C[/math] это логическая схема.


Теорема:
[math]CIRCVAL[/math][math]\mathrm{P}[/math]-полная задача.[4]

Ссылки