Редактирование: Класс P

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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 ==
{{Теорема
+
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}</tex>.
|statement =
+
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>\mathrm{L} \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P^L}</tex>.
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \in \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</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 =
 
|statement =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
+
Если <tex>L \in \mathrm{P}</tex>, то <tex>L^* \in \mathrm{P}</tex>.
 
|proof =
 
|proof =
Понятно, что <tex>\mathrm{P} \subset \mathrm{P}^D</tex>. Докажем, что <tex>\mathrm{P}^D \subset \mathrm{P}</tex>.
+
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</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>q(w):</tex>
 
     <tex>n = |w|</tex>
 
     <tex>n = |w|</tex>
     <tex>endPoses = \{0\}</tex>  //позиции, где могут заканчиваться слова, принадлежащие <tex>L_1</tex>
+
     <tex>endPoses = \{0\}</tex>  //позиции, где могут заканчиваться слова, принадлежащие <tex>L</tex>
 
     for (<tex>i = 1 \ldots n</tex>)
 
     for (<tex>i = 1 \ldots n</tex>)
 
         for (<tex>j \in endPoses</tex>)
 
         for (<tex>j \in endPoses</tex>)
Строка 64: Строка 32:
 
             }
 
             }
 
     return false
 
     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>.
+
Худшая оценка времени работы разрешителя <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^* \in \mathrm{P}</tex>.
 
}}
 
}}
  
== Примеры задач и языков из P ==
+
== Соотношение классов Reg и 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 =
 
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
+
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
 
|proof =
 
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
+
<tex>Reg \subset TS(n, 1) \subset P</tex>
 +
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени, и по памяти.
 
}}
 
}}
  
 
+
== Соотношение классов CFL и P ==
 
{{Теорема
 
{{Теорема
 
|statement =
 
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
+
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
 
|proof =
 
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
+
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
 
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
 
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
 
}}
 
}}
  
== P-полные задачи ==
+
== Примеры задач и языков из P ==
Говоря про <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полноту]], мы, как правило, подразумеваем <tex>\mathrm{P}</tex>-полноту относительно <tex>\widetilde{\mathrm{L}}</tex>-сведения.<ref>[[Классы L, NL, coNL. NL-полнота задачи о достижимости]]</ref>
+
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
 +
* определение связности графов;
 +
* вычисление наибольшего общего делителя;
 +
* задача линейного программирования;
 +
* проверка простоты числа.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal, N.Kayal, N.Saxena, "Primes is in P"]</ref>
 +
 
 +
 
 +
По [[теорема о временной иерархии|теореме о временной иерархии]] существуют задачи и не из <tex>P</tex>.
  
{{Определение
+
== Задача равенства P и NP ==
|definition=
+
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день.  
<tex>CIRCVAL = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</tex> это логическая схема.
 
}}
 
  
{{Теорема
+
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</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/>
  
[[Категория: Классы сложности]]
+
[[Категория: Теория сложности]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: