Изменения

# Замкнутость {{Теорема|statement =Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex> L \in \mathrm{P} , M \le L \Rightarrow M \in \mathrm{P}</tex>.# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. proof =Пусть <tex>p</tex>\mathrm{L} \subset \mathrm{P---} \Rightarrow \mathrm{P}=\mathrm{P^разрешитель <tex>L}</tex>, работающий за полиномиальное время.# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 (M \leq L) \overset{\underset{\mathrm{def}}{}}{\iff} ( \exists f \in \mathrm{\widetilde{P}} : w \in M \Leftrightarrow f(w) \in L ) </tex>, то: .Построим разрешитель <tex>L_1 \cup L_2 \in \mathrm{P}q</tex>, для языка <tex>L_1 \cap L_2 \in \mathrm{P}M</tex>, . <tex>L_1 L_2 \in \mathrm{P}q(w):</tex>, if (<tex>L_1^* \in \mathrm{P}p(f(w))</tex> и ) return true return falseРазрешитель <tex>\overline{L_1} \in \mathrm{P}q</tex>работает за полиномиальное время, так как композиция полиномов есть полином. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).}}

 {{ЛеммаТеорема

Если <tex>L D \in subseteq \mathrm{P}\Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, то из этого следует, что <tex>L^* \in mathrm{P}=\mathrm{P^P}</tex>.

Понятно, что <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>LL_1^*</tex>.

<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>LL_1</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>LL_1^* \in \mathrm{P}</tex>.

== Соотношение классов 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>.  

== Примеры задач и языков из P -полные задачи ==Класс Говоря про <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полноту]], мы, разрешимых за полиномиальное время достаточно широккак правило, вот несколько его представителей:* определение связности графов;* вычисление наибольшего общего делителя;* задача линейного программирования;* проверка простоты числаподразумеваем <tex>\mathrm{P}</tex>-полноту относительно <tex>\widetilde{\mathrm{L}}</tex>-сведения.<ref>[http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf M.Argawal[Классы L, N.KayalNL, NcoNL.Saxena, "Primes is in P"NL-полнота задачи о достижимости]]</ref> 

По [[теорема о временной иерархии{{Определение|теореме о временной иерархии]] существуют задачи и не из definition=<tex>CIRCVAL = \mathrm{P\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</tex> это логическая схема.}}

== Задача равенства P и NP ={{Теорема|statement =Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>\mathrm{P}CIRCVAL</tex> и <tex>\mathrm{NP{---}</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день.  Легко показать, что, по определению <tex>\mathrm{P}</tex>, <tex>\mathrm{P}\subset \mathrm{NP}</tex>, так как для любой задачи класса -полная задача.<tex>P</texref> существует соответствующая [http://ruwww.math.wikipediasc.orgedu/~cooper/wikimath778C/%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 ДМТ]abct.pdf S.Arora, которая является частным случаем [[Недетерминированные вычисленияB. Классы NP и Σ₁|НМТ]Barak, "Computational Complexity: A Modern Approach"], а значит задача, по определению, будет входить в класс <tex/ref>\mathrm{NP}}</tex>.

[[Категория: Теория Классы сложности]]