Изменения

'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<tex>\mathrm{P } = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.

Итого, язык <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 к изменению модели вычислений ==Машина Тьюринга может симулировать другие модели вычислений (например, языки программирования) с не более чем полиномиальным замедлением. Благодаря этому, класс <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> устойчив и в обратном преобразовании модели вычислений.

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

if (|<tex>p(f(w| = 0))</tex>)

Мне кажетсяРазрешитель <tex>q</tex> работает за полиномиальное время, он за так как композиция полиномов есть полином работает. Завтра формально напишу, почему (если смогу).}} 

Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, то есть: из этого следует, что <tex>Reg \subset mathrm{P}=\mathrm{P^P}</tex>.

Понятно, что <tex>Reg \mathrm{P} \subset TS(n\mathrm{P}^D</tex>. Докажем, 1) что <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>TSp</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>.

Класс [[Контекстно-свободные грамматики<tex>\mathrm{P}</tex> замкнут относительно операций объединения, пересечения, выводконкатенации, лево- замыкания Клини и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс дополнения. Если <tex>L_1, L_2 \in \mathrm{P}</tex>, то есть: <tex>CFL 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 \subset mathrm{P}</tex>.

Докажем замкнутость замыкания Клини. Остальные доказательства строятся аналогично. Пусть <tex>p</tex> {{---}} разрешитель <tex>L_1</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L_1^*</tex>. <tex>q(w):</tex> <tex>n = |w|</tex> <tex>CFL endPoses = \{0\subset TS}</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^32 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L_1^2) * \in \subset mathrm{P}</tex>Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].

По == P-полные задачи ==Говоря про <tex>\mathrm{P}</tex>-[[теорема о временной иерархииСведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|теореме о временной иерархииполноту]] существуют и задачи не из , мы, как правило, подразумеваем <tex>\mathrm{P}</tex>-полноту относительно <tex>\widetilde{\mathrm{L}}</tex>-сведения.<ref>[[Классы L, NL, coNL. NL-полнота задачи о достижимости]]</ref>

{{Определение|definition=<tex>CIRCVAL = Задача равенства P и NP \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) ==Одним из центральных вопросов теории сложности является вопрос о равенстве классов 1\}</tex>, где <tex>PC</tex> и [[NP]], не разрешенный по сей деньэто логическая схема. }}

Легко показать, что, по определению {{Теорема|statement =<tex>PCIRCVAL</tex>, {{---}} <tex> \mathrm{P \subset NP}</tex>, так как для любой задачи класса -полная задача.<texref>P<[http://www.math.sc.edu/~cooper/math778C/tex> существует соответствующая ДМТabct.pdf S.Arora, которая является частным случаем НМТ, а значит задача, по определениюB.Barak, будет входить в класс <tex>NP"Computational Complexity: A Modern Approach"]</texref>.}}