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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства класса P)
(Свойства класса P: Теперь чёткое доказательство замкнутости замыкания Клини)
Строка 17: Строка 17:
 
#* Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично). Пусть <tex>L_1 \in P</tex>, <tex>p_1</tex> {{---}} разрешитель <tex>L_1</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L_1^*</tex>.
 
#* Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично). Пусть <tex>L_1 \in P</tex>, <tex>p_1</tex> {{---}} разрешитель <tex>L_1</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L_1^*</tex>.
 
  <tex>q(w):</tex>
 
  <tex>q(w):</tex>
     if (|w| = 0)
+
     <tex>n = |w|</tex>
        return true
+
    <tex>endPoses = \{0\}</tex>  //позиции, где могут заканчиваться слова, принадлежащие <tex>L_1</tex>
     for (<tex>i = 1 \ldots |w|</tex>)
+
     for (<tex>i = 1 \ldots n</tex>)
         if (<tex>p_1(w[1..i])</tex> and <tex>q(w[i + 1..|w|])</tex>)
+
         for (<tex>j \in endPoses</tex>)
            return true
+
            if (<tex>p_1(w[j+1 \ldots i])</tex>) {
 +
                if (<tex>i = n</tex>)
 +
                    return true
 +
                <tex>endPoses</tex> <tex>\cup = \{i\}</tex>
 +
            }
 
     return false
 
     return false
Мне кажется, он за полином работает. Завтра формально напишу, почему (если смогу).
+
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 O(p_1(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов. Итого, разрешитель <tex>q</tex> работает за полиномиальное время. Значит <tex>L_1^* \in P</tex>.
  
 
== Соотношение классов Reg и P ==
 
== Соотношение классов Reg и P ==

Версия 17:15, 2 мая 2012

Определение

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


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

  1. Замкнутость относительно сведения по Карпу. [math] L \in P , M \le L \Rightarrow M \in P[/math]
  2. Замкнутость относительно сведения по Куку. [math]L \subset P \Rightarrow P=P^L[/math].
  3. Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если [math]L_1, L_2 \in P[/math], то: [math]L_1 \cup L_2 \in P[/math], [math]L_1 \cap L_2 \in P[/math], [math]L_1 L_2 \in P[/math], [math]L_1^* \in P[/math] и [math]\overline{L_1} \in P[/math].
    • Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично). Пусть [math]L_1 \in P[/math], [math]p_1[/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_1(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_1(w))[/math], так как в множестве [math]endPoses[/math] может быть максимум [math]n[/math] элементов. Итого, разрешитель [math]q[/math] работает за полиномиальное время. Значит [math]L_1^* \in P[/math].

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

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

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

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

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

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

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

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

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

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

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


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

Задача равенства P и NP

Одним из центральных вопросов теории сложности является вопрос о равенстве классов [math]P[/math] и NP, не разрешенный по сей день.

Легко показать, что, по определению [math]P[/math], [math] P \subset NP[/math], так как для любой задачи класса [math]P[/math] существует соответствующая ДМТ, которая является частным случаем НМТ, а значит задача, по определению, будет входить в класс [math]NP[/math].

Ссылки