202
правки
Изменения
Нет описания правки
# если на вход машине <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> устойчив и в обратном преобразовании модели вычислений.
== Свойства класса P ==
{{ЛеммаТеорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \in \mathrm{P}</tex>.
{{ЛеммаТеорема
|statement =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</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>.
}}
== Соотношение классов 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 =
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}
{{Теорема
|statement =
}}
== Примеры задач и языков из 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 = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</tex> это логическая схема.
}}
== Ссылки ==
<references/>
[[Категория: Теория Классы сложности]]
