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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 76 промежуточных версий 11 участников)
Строка 1: Строка 1:
В теории сложности '''Класс''' <tex>P</tex> &mdash;  класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть  
+
== Определение ==
 +
{{Определение
 +
|definition=
 +
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:
 +
<tex>\mathrm{P} = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.
 +
}}
  
<tex>P=\bigcup_{i=0}^{\infty} DTIME(in^i)=\bigcup_{i=0}^{\infty}\bigcup_{k=0}^{\infty} DTIME(in^k)</tex>.  
+
Итого, язык <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 к изменению модели вычислений ==
Язык L лежит в классе <tex>P</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:
+
Машина Тьюринга может симулировать другие модели вычислений (например, языки программирования) с не более чем полиномиальным замедлением. Благодаря этому, класс <tex>\mathrm{P}</tex> на этих моделях не становится шире.
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных
 
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его
 
# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его
 
  
==Свойства класса <tex>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> устойчив и в обратном преобразовании модели вычислений.
# Замкнутость относительно дополнений. <tex> L \in P \Rightarrow \overline L \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>P</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>.
 +
}}
 +
 
 +
== Примеры задач и языков из 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>, так как из [[теорема о временной иерархии|теоремы о временной иерархии]] следует, что <tex>\exists L \in \mathrm{EXP}\setminus\mathrm{P}</tex>.
 +
 
 +
 
 +
{{Теорема
 +
|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>P</tex>.
 
  
==Задача равенства <tex>P</tex> и <tex>NP</tex>==
+
{{Теорема
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и [[NP]], не разрешенный по сей день.  
+
|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>
 +
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
 +
}}
  
Легко показать, что по определению, <tex> P \subset NP</tex>, так как достаточно для любой задачи класса <tex>P</tex> существует соответствующая ДМТ, которая является частным случаем НМТ, а значит задача по определению будет входить в класс <tex>NP</tex>
+
== P-полные задачи ==
 +
Говоря про <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полноту]], мы, как правило, подразумеваем <tex>\mathrm{P}</tex>-полноту относительно <tex>\widetilde{\mathrm{L}}</tex>-сведения.<ref>[[Классы L, NL, coNL. NL-полнота задачи о достижимости]]</ref>
  
<ref>E. Miller, The Sun, (New York: Academic Press, 2005), 23-5.</ref>
+
{{Определение
 +
|definition=
 +
<tex>CIRCVAL = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</tex> это логическая схема.
 +
}}
  
==Ссылки==
+
{{Теорема
 +
|statement =
 +
<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>
 +
}}
 +
 
 +
== Ссылки ==
 
<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]

Ссылки