Викиконспекты - Вклад участника [ru]

Участник:Tsar

2014-10-31T08:39:29Z

Tsar: I am year2009

Волков Иоанн Русланович (year2009)

volkov.ioann@gmail.com

Заглавная страница

2013-06-15T09:11:28Z

Tsar: Правильные тирешки

Добро пожаловать на сайт [[Вики-конспекты|вики-конспектов]]!

= Проверяемые конспекты =

==Преподаватель [[Андрей Сергеевич Станкевич]]==

* [[Дискретная математика, алгоритмы и структуры данных|Дискретная математика, алгоритмы и структуры данных — 1, 2, 3 и 4 семестр]]
* [[Теория формальных языков|Теория формальных языков — 5 семестр]]
* [[Теория сложности|Теория сложности — 6 семестр]]
* [[Методы трансляции|Методы трансляции — 6 семестр]]

==Преподаватель [[Федор Николаевич Царев]]==
* [[Эволюционные алгоритмы|Эволюционные алгоритмы — 10 семестр]]

==Преподаватель [[Корнеев Георгий Александрович]]==
* [[Язык программирования Java|Язык программирования Java — 2 семестр]]

= Непроверяемые конспекты =

*[[Алгебра и геометрия 1 курс | Алгебра и геометрия — 1, 2 семестр]]
*[[Математический анализ 1 курс | Математический анализ — 1, 2 семестр]]
*[[Математический анализ 2 курс | Математический анализ — 3, 4 семестр]]
*[[Математическая логика|Математическая логика — 3 семестр]]
*[[Участник:Qwerty787788/плюсы3сем | С++ — 3 семестр]]
*[[Вычислительная геометрия|Вычислительная геометрия — 3, 4 семестр]]
*[[Assembler|Assembler — 4 семестр]]
*[[Алгоритмы алгебры и теории чисел|Алгоритмы алгебры и теории чисел — 4 семестр]]
*[[Функциональный_анализ_3_курс | Функциональный анализ — 5, 6 семестр]]
*[[Параллельное программирование|Параллельное программирование — 6 семестр]]

Теорема Лаутемана

2012-06-25T11:27:23Z

Tsar: /* Теорема */ Там вроде не нужно "-2"

{{Лемма
| statement = <tex>\mathrm{BPP} = \mathrm{coBPP}</tex>
| proof =
Рассмотрим <tex>L \in \mathrm{BPP}</tex>. Существует такая программа <tex>p</tex>, что <tex>P(p(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Покажем, что <tex>\overline{L} \in \mathrm{BPP}</tex>. Для этого рассмотрим следующую программу:
<tex>p'(x):</tex>
<tex>return (1 - p(x));</tex>
<tex>P(p'(x) = [x \in \overline{L}]) = P(p(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Таким образом <tex>\overline{L} \in \mathrm{BPP}</tex>.
#<tex>L \in \mathrm{BPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{coBPP}</tex>. Получаем <tex>\mathrm{BPP} \subset \mathrm{coBPP}</tex>.
#<tex>L \in \mathrm{coBPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{BPP}</tex>. Получаем <tex>\mathrm{coBPP} \subset \mathrm{BPP}</tex>.
}}

==Теорема==
{{ Теорема
| about = Лаутеман
| statement = <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}</tex>
| proof =

Из того, что класс <tex>\mathrm{BPP}</tex> замкнут относительно дополнения и <tex>\mathrm{co\Sigma_2} = \mathrm{\Pi_2}</tex>, следует, что достаточно доказать включение <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2}</tex>.

<tex>\mathrm{BPP}</tex> можно определить как множество таких языков <tex>L</tex>, что <tex>x \in L</tex> тогда и только тогда, когда существует «много» таких вероятностных лент <tex>y</tex>, что <tex>M(x,y)</tex>, где <tex>M</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга | вероятностная машина Тьюринга]] для <tex>L</tex>. <tex>\mathrm{\Sigma_2}</tex> — множество таких языков <tex>L</tex>, что <tex>x \in L</tex> тогда и только тогда, когда существует такой <tex>y</tex>, что для любого <tex>z</tex> <tex>R(x, y, z)</tex>. Таким образом, необходимо уметь записывать «существует много» с помощью кванторов <tex>\exists</tex>, <tex>\forall</tex>.

Рассмотрим язык <tex>G = \{0, 1\}^t</tex> для некоторого <tex>t</tex>. Определим операцию <tex>\oplus</tex> над словами из этого языка как побитовое исключающее или.

Назовем <tex>X</tex>, содержащееся в <tex>G</tex>, <tex>k</tex>-большим, если существует такой набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>, что <tex>\bigcup\limits_{i=1}^{k} g_i \oplus X = G</tex>. Иначе будем называть <tex>X</tex> — <tex>k</tex>-маленьким.

Если <tex>|X| < \frac{2^t}{k}</tex>, то <tex>X</tex> является <tex>k</tex>-маленьким (так как <tex>k</tex> копий <tex>X</tex> не смогут покрыть <tex>G</tex>). Найдем достаточное условие, при котором <tex>X</tex> является <tex>k</tex>-большим.

Воспользуемся утверждением, что если вероятность <tex>P(x \in A) > 0</tex>, то существует <tex>x</tex> из <tex>A</tex>. Для этого
выберем случайно набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>.

<tex>P(\bigcup\limits_{i=1}^{k} g_i \oplus X \not = G) = P(\exists y \not \in \bigcup\limits_{i=1}^{k} g_i \oplus X) = P(\bigvee\limits_{i=1}^{2^t} y_i \not \in \bigcup\limits_{j=1}^{k} g_j \oplus X)</tex> <tex>\leqslant 2^t P(y \not \in \bigcup\limits_{i=1}^{k} g_i \oplus X) = 2^t P(\bigwedge\limits_{i=1}^{k} y \oplus g_i \not \in X) = 2^t \left(P(y \not \in X)\right)^k = 2^t \left(1 - \frac{|X|}{2^t}\right)^k</tex>.

Если <tex>2^t\left(1 - \frac{|X|}{2^t}\right)^k < 1</tex>, то существует такой набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>, что <tex>\bigcup\limits_{i=1}^{k} g_i \oplus X = G</tex>, то есть <tex>X</tex> — <tex>k</tex>-большое.

Рассмотрим язык <tex>L \in \mathrm{BPP}</tex>. Тогда существует вероятностная машина Тьюринга <tex>m</tex>, такая что <tex>P(m(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Пусть <tex>m</tex> использует <tex>r(n)</tex> бит случайной ленты. По аналогии c [[Классы BPP и PP|доказательством]] <tex>\mathrm{BPP} = \mathrm{BPP_{strong}}</tex>, построим машину <tex>M</tex>, которая запускает <tex>m</tex> достаточное число раз, чтобы получить вероятность ошибки <tex>\frac{1}{2^{p(n)}}</tex>, где <tex>p(n)</tex> это некоторый полином, который будет определён позднее. Будет достаточно <tex>c p(n)^2</tex> запусков. Соответственно, <tex>M</tex> использует <tex>t(n) = c r(n) p(n)^2</tex> бит случайной ленты, <tex>P(M(x) = [x \in L]) \geqslant 1 - \frac{1}{2^{p(n)}}</tex>.

Зафиксируем <tex>x</tex>. Возьмем <tex>G = \{0, 1\}^{t(n)}</tex>. Рассмотрим множество <tex>A_x = \{r \in G \bigm| M(x,r) = 1\}</tex>. Подберем теперь <tex>p(n)</tex> и <tex>k</tex> так, чтобы <tex>x \in L \Leftrightarrow A_x</tex> — <tex>k</tex>-большое.

Если <tex>x \in L</tex>, то <tex>P(M(x) = 1) = \frac{|A_x|}{2^{t(n)}} \geqslant 1 - \frac{1}{2^{p(n)}} \Rightarrow |A_x| \geqslant 2^{t(n)} \left( 1 - \frac{1}{2^{p(n)}} \right)</tex>. Значит <tex>2^{t(n)} \left( 1 - \frac{|A_x|}{2^{t(n)}} \right)^k \leqslant 2^{t(n) - kp(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-большим потребуем <tex>2^{t(n) - kp(n)} < 1</tex>.

Если <tex>x \not \in L</tex>, то <tex>P(M(x) = 1) = \frac{|A_x|}{2^{t(n)}} \leqslant \frac{1}{2^{p(n)}} \Rightarrow |A_x| \leqslant 2^{t(n) - p(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-маленьким потребуем <tex>2^{t(n) - p(n)} < \frac{2^{t(n)}}{k}</tex>.

Выберем <tex>p(n)</tex> так, чтобы <tex>\frac{t(n)}{p(n)} < 2^{p(n)}</tex> (то есть <tex>c r(n) p(n) < 2^{p(n)}</tex>) и <tex>k = \lceil \frac{t(n)}{p(n)} \rceil + 1 = c r(n) p(n) + 1</tex>. Получаем <tex>\frac{t(n)}{p(n)} < k < 2^{p(n)}</tex>, то есть <tex>x \in L \Leftrightarrow A_x</tex> — <tex>k</tex>-большое.

Таким образом, <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \subset G</tex> : <tex>\forall y \in G</tex> <tex>\left( \bigvee\limits_{i=1}^{k} y \in g_i \oplus A_x \right) </tex>. Заметив, что <tex>y \in g_i \oplus A_x \Leftrightarrow y \oplus g_i \in A_x \Leftrightarrow M(x, y \oplus g_i)</tex>, получаем <tex>L \in \Sigma_2</tex>, <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2}</tex> и <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы PH, Σ и Π]]
*[[Классы BPPweak и BPPstrong]]

== Литература ==
* ''Sanjeev Arora, Boaz Barak''. [http://www.cs.princeton.edu/theory/complexity Computational Complexity: A Modern Approach]

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

Теорема Лаутемана

2012-06-25T11:25:17Z

Tsar: /* Теорема */ Поправки, вроде финальные для этого куска

{{Лемма
| statement = <tex>\mathrm{BPP} = \mathrm{coBPP}</tex>
| proof =
Рассмотрим <tex>L \in \mathrm{BPP}</tex>. Существует такая программа <tex>p</tex>, что <tex>P(p(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Покажем, что <tex>\overline{L} \in \mathrm{BPP}</tex>. Для этого рассмотрим следующую программу:
<tex>p'(x):</tex>
<tex>return (1 - p(x));</tex>
<tex>P(p'(x) = [x \in \overline{L}]) = P(p(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Таким образом <tex>\overline{L} \in \mathrm{BPP}</tex>.
#<tex>L \in \mathrm{BPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{coBPP}</tex>. Получаем <tex>\mathrm{BPP} \subset \mathrm{coBPP}</tex>.
#<tex>L \in \mathrm{coBPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{BPP}</tex>. Получаем <tex>\mathrm{coBPP} \subset \mathrm{BPP}</tex>.
}}

==Теорема==
{{ Теорема
| about = Лаутеман
| statement = <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}</tex>
| proof =

Из того, что класс <tex>\mathrm{BPP}</tex> замкнут относительно дополнения и <tex>\mathrm{co\Sigma_2} = \mathrm{\Pi_2}</tex>, следует, что достаточно доказать включение <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2}</tex>.

<tex>\mathrm{BPP}</tex> можно определить как множество таких языков <tex>L</tex>, что <tex>x \in L</tex> тогда и только тогда, когда существует «много» таких вероятностных лент <tex>y</tex>, что <tex>M(x,y)</tex>, где <tex>M</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга | вероятностная машина Тьюринга]] для <tex>L</tex>. <tex>\mathrm{\Sigma_2}</tex> — множество таких языков <tex>L</tex>, что <tex>x \in L</tex> тогда и только тогда, когда существует такой <tex>y</tex>, что для любого <tex>z</tex> <tex>R(x, y, z)</tex>. Таким образом, необходимо уметь записывать «существует много» с помощью кванторов <tex>\exists</tex>, <tex>\forall</tex>.

Рассмотрим язык <tex>G = \{0, 1\}^t</tex> для некоторого <tex>t</tex>. Определим операцию <tex>\oplus</tex> над словами из этого языка как побитовое исключающее или.

Назовем <tex>X</tex>, содержащееся в <tex>G</tex>, <tex>k</tex>-большим, если существует такой набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>, что <tex>\bigcup\limits_{i=1}^{k} g_i \oplus X = G</tex>. Иначе будем называть <tex>X</tex> — <tex>k</tex>-маленьким.

Если <tex>|X| < \frac{2^t}{k}</tex>, то <tex>X</tex> является <tex>k</tex>-маленьким (так как <tex>k</tex> копий <tex>X</tex> не смогут покрыть <tex>G</tex>). Найдем достаточное условие, при котором <tex>X</tex> является <tex>k</tex>-большим.

Воспользуемся утверждением, что если вероятность <tex>P(x \in A) > 0</tex>, то существует <tex>x</tex> из <tex>A</tex>. Для этого
выберем случайно набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>.

<tex>P(\bigcup\limits_{i=1}^{k} g_i \oplus X \not = G) = P(\exists y \not \in \bigcup\limits_{i=1}^{k} g_i \oplus X) = P(\bigvee\limits_{i=1}^{2^t} y_i \not \in \bigcup\limits_{j=1}^{k} g_j \oplus X)</tex> <tex>\leqslant 2^t P(y \not \in \bigcup\limits_{i=1}^{k} g_i \oplus X) = 2^t P(\bigwedge\limits_{i=1}^{k} y \oplus g_i \not \in X) = 2^t \left(P(y \not \in X)\right)^k = 2^t \left(1 - \frac{|X|}{2^t}\right)^k</tex>.

Если <tex>2^t\left(1 - \frac{|X|}{2^t}\right)^k < 1</tex>, то существует такой набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>, что <tex>\bigcup\limits_{i=1}^{k} g_i \oplus X = G</tex>, то есть <tex>X</tex> — <tex>k</tex>-большое.

Рассмотрим язык <tex>L \in \mathrm{BPP}</tex>. Тогда существует вероятностная машина Тьюринга <tex>m</tex>, такая что <tex>P(m(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Пусть <tex>m</tex> использует <tex>r(n)</tex> бит случайной ленты. По аналогии c [[Классы BPP и PP|доказательством]] <tex>\mathrm{BPP} = \mathrm{BPP_{strong}}</tex>, построим машину <tex>M</tex>, которая запускает <tex>m</tex> достаточное число раз, чтобы получить вероятность ошибки <tex>\frac{1}{2^{p(n)}}</tex>, где <tex>p(n)</tex> это некоторый полином, который будет определён позднее. Будет достаточно <tex>c p(n)^2</tex> запусков. Соответственно, <tex>M</tex> использует <tex>t(n) = c r(n) p(n)^2</tex> бит случайной ленты, <tex>P(M(x) = [x \in L]) \geqslant 1 - \frac{1}{2^{p(n)}}</tex>.

Зафиксируем <tex>x</tex>. Возьмем <tex>G = \{0, 1\}^{t(n)}</tex>. Рассмотрим множество <tex>A_x = \{r \in G \bigm| M(x,r) = 1\}</tex>. Подберем теперь <tex>p(n)</tex> и <tex>k</tex> так, чтобы <tex>x \in L \Leftrightarrow A_x</tex> — <tex>k</tex>-большое.

Если <tex>x \in L</tex>, то <tex>P(M(x) = 1) = \frac{|A_x|}{2^{t(n)}} \geqslant 1 - \frac{1}{2^{p(n)}} \Rightarrow |A_x| \geqslant 2^{t(n)} \left( 1 - \frac{1}{2^{p(n)}} \right)</tex>. Значит <tex>2^{t(n)} \left( 1 - \frac{|A_x|}{2^{t(n)}} \right)^k \leqslant 2^{t(n) - kp(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-большим потребуем <tex>2^{t(n) - kp(n)} < 1</tex>.

Если <tex>x \not \in L</tex>, то <tex>P(M(x) = 1) = \frac{|A_x|}{2^{t(n)}} \leqslant \frac{1}{2^{p(n)}} \Rightarrow |A_x| \leqslant 2^{t(n) - p(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-маленьким потребуем <tex>2^{t(n) - p(n)} < \frac{2^{t(n)}}{k}</tex>.

Выберем <tex>p(n)</tex> так, чтобы <tex>\frac{t(n)}{p(n)} < 2^{p(n)} - 2</tex> (то есть <tex>c r(n) p(n) < 2^{p(n)}</tex>) и <tex>k = \lceil \frac{t(n)}{p(n)} \rceil + 1 = c r(n) p(n) + 1</tex>. Получаем <tex>\frac{t(n)}{p(n)} < k < 2^{p(n)}</tex>, то есть <tex>x \in L \Leftrightarrow A_x</tex> — <tex>k</tex>-большое.

Таким образом, <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \subset G</tex> : <tex>\forall y \in G</tex> <tex>\left( \bigvee\limits_{i=1}^{k} y \in g_i \oplus A_x \right) </tex>. Заметив, что <tex>y \in g_i \oplus A_x \Leftrightarrow y \oplus g_i \in A_x \Leftrightarrow M(x, y \oplus g_i)</tex>, получаем <tex>L \in \Sigma_2</tex>, <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2}</tex> и <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы PH, Σ и Π]]
*[[Классы BPPweak и BPPstrong]]

== Литература ==
* ''Sanjeev Arora, Boaz Barak''. [http://www.cs.princeton.edu/theory/complexity Computational Complexity: A Modern Approach]

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

Теорема Лаутемана

2012-06-25T11:21:59Z

Tsar: /* Теорема */ Поправки продолжаются, ещё не всё

{{Лемма
| statement = <tex>\mathrm{BPP} = \mathrm{coBPP}</tex>
| proof =
Рассмотрим <tex>L \in \mathrm{BPP}</tex>. Существует такая программа <tex>p</tex>, что <tex>P(p(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Покажем, что <tex>\overline{L} \in \mathrm{BPP}</tex>. Для этого рассмотрим следующую программу:
<tex>p'(x):</tex>
<tex>return (1 - p(x));</tex>
<tex>P(p'(x) = [x \in \overline{L}]) = P(p(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Таким образом <tex>\overline{L} \in \mathrm{BPP}</tex>.
#<tex>L \in \mathrm{BPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{coBPP}</tex>. Получаем <tex>\mathrm{BPP} \subset \mathrm{coBPP}</tex>.
#<tex>L \in \mathrm{coBPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{BPP}</tex>. Получаем <tex>\mathrm{coBPP} \subset \mathrm{BPP}</tex>.
}}

==Теорема==
{{ Теорема
| about = Лаутеман
| statement = <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}</tex>
| proof =

Из того, что класс <tex>\mathrm{BPP}</tex> замкнут относительно дополнения и <tex>\mathrm{co\Sigma_2} = \mathrm{\Pi_2}</tex>, следует, что достаточно доказать включение <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2}</tex>.

<tex>\mathrm{BPP}</tex> можно определить как множество таких языков <tex>L</tex>, что <tex>x \in L</tex> тогда и только тогда, когда существует «много» таких вероятностных лент <tex>y</tex>, что <tex>M(x,y)</tex>, где <tex>M</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга | вероятностная машина Тьюринга]] для <tex>L</tex>. <tex>\mathrm{\Sigma_2}</tex> — множество таких языков <tex>L</tex>, что <tex>x \in L</tex> тогда и только тогда, когда существует такой <tex>y</tex>, что для любого <tex>z</tex> <tex>R(x, y, z)</tex>. Таким образом, необходимо уметь записывать «существует много» с помощью кванторов <tex>\exists</tex>, <tex>\forall</tex>.

Рассмотрим язык <tex>G = \{0, 1\}^t</tex> для некоторого <tex>t</tex>. Определим операцию <tex>\oplus</tex> над словами из этого языка как побитовое исключающее или.

Назовем <tex>X</tex>, содержащееся в <tex>G</tex>, <tex>k</tex>-большим, если существует такой набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>, что <tex>\bigcup\limits_{i=1}^{k} g_i \oplus X = G</tex>. Иначе будем называть <tex>X</tex> — <tex>k</tex>-маленьким.

Если <tex>|X| < \frac{2^t}{k}</tex>, то <tex>X</tex> является <tex>k</tex>-маленьким (так как <tex>k</tex> копий <tex>X</tex> не смогут покрыть <tex>G</tex>). Найдем достаточное условие, при котором <tex>X</tex> является <tex>k</tex>-большим.

Воспользуемся утверждением, что если вероятность <tex>P(x \in A) > 0</tex>, то существует <tex>x</tex> из <tex>A</tex>. Для этого
выберем случайно набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>.

<tex>P(\bigcup\limits_{i=1}^{k} g_i \oplus X \not = G) = P(\exists y \not \in \bigcup\limits_{i=1}^{k} g_i \oplus X) = P(\bigvee\limits_{i=1}^{2^t} y_i \not \in \bigcup\limits_{j=1}^{k} g_j \oplus X)</tex> <tex>\leqslant 2^t P(y \not \in \bigcup\limits_{i=1}^{k} g_i \oplus X) = 2^t P(\bigwedge\limits_{i=1}^{k} y \oplus g_i \not \in X) = 2^t \left(P(y \not \in X)\right)^k = 2^t \left(1 - \frac{|X|}{2^t}\right)^k</tex>.

Если <tex>2^t\left(1 - \frac{|X|}{2^t}\right)^k < 1</tex>, то существует такой набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>, что <tex>\bigcup\limits_{i=1}^{k} g_i \oplus X = G</tex>, то есть <tex>X</tex> — <tex>k</tex>-большое.

Рассмотрим язык <tex>L \in \mathrm{BPP}</tex>. Тогда существует вероятностная машина Тьюринга <tex>m</tex>, такая что <tex>P(m(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Пусть <tex>m</tex> использует <tex>r(n)</tex> бит случайной ленты. По аналогии c [[Классы BPP и PP|доказательством]] <tex>\mathrm{BPP} = \mathrm{BPP_{strong}}</tex>, построим машину <tex>M</tex>, которая запускает <tex>m</tex> достаточное число раз, чтобы получить вероятность ошибки <tex>\frac{1}{2^{p(n)}}</tex>, где <tex>p(n)</tex> это некоторый полином, который будет определён позднее. Будет достаточно <tex>c p(n)^2</tex> запусков. Соответственно, <tex>M</tex> использует <tex>t(n) = c r(n) p(n)^2</tex> бит случайной ленты, <tex>P(M(x) = [x \in L]) \geqslant 1 - \frac{1}{2^{p(n)}}</tex>.

Зафиксируем <tex>x</tex>. Возьмем <tex>G = \{0, 1\}^{t(n)}</tex>. Рассмотрим множество <tex>A_x = \{r \in G \bigm| M(x,r) = 1\}</tex>. Подберем теперь <tex>p(n)</tex> и <tex>k</tex> так, чтобы <tex>x \in L \Leftrightarrow A_x</tex> — <tex>k</tex>-большое.

Если <tex>x \in L</tex>, то <tex>P(M(x) = 1) = \frac{|A_x|}{2^{t(n)}} \geqslant 1 - \frac{1}{2^{p(n)}} \Rightarrow |A_x| \geqslant 2^{t(n)} \left( 1 - \frac{1}{2^{p(n)}} \right)</tex>. Значит <tex>2^{t(n)} \left( 1 - \frac{|A_x|}{2^{t(n)}} \right)^k \leqslant 2^{t(n) - kp(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-большим потребуем <tex>2^{t(n) - kp(n)} < 1</tex>.

Если <tex>x \not \in L</tex>, то <tex>P(M(x) = 1) = \frac{|A_x|}{2^{t(n)}} \leqslant \frac{1}{2^{p(n)}} \Rightarrow |A_x| \leqslant 2^{t(n) - p(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-маленьким потребуем <tex>2^{t(n) - p(n)} < \frac{2^{t(n)}}{k}</tex>.

Выберем <tex>p(n)</tex> так, чтобы <tex>\frac{t(n)}{p(n)} < 2^{p(n)} - 2</tex> и <tex>k = \lceil \frac{t(n)}{p(n)} \rceil + 1</tex>. Получаем <tex>\frac{t(n)}{p(n)} < k < 2^{p(n)}</tex>, то есть <tex>x \in L \Leftrightarrow A_x</tex> — <tex>k</tex>-большое.

Таким образом, <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \subset G</tex> : <tex>\forall y \in G</tex> <tex>\left( \bigvee\limits_{i=1}^{k} y \in g_i \oplus A_x \right) </tex>. Заметив, что <tex>y \in g_i \oplus A_x \Leftrightarrow y \oplus g_i \in A_x \Leftrightarrow M(x, y \oplus g_i)</tex>, получаем <tex>L \in \Sigma_2</tex>, <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2}</tex> и <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы PH, Σ и Π]]
*[[Классы BPPweak и BPPstrong]]

== Литература ==
* ''Sanjeev Arora, Boaz Barak''. [http://www.cs.princeton.edu/theory/complexity Computational Complexity: A Modern Approach]

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

Теорема Лаутемана

2012-06-25T11:09:55Z

Tsar: Попытка исправить

{{Лемма
| statement = <tex>\mathrm{BPP} = \mathrm{coBPP}</tex>
| proof =
Рассмотрим <tex>L \in \mathrm{BPP}</tex>. Существует такая программа <tex>p</tex>, что <tex>P(p(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Покажем, что <tex>\overline{L} \in \mathrm{BPP}</tex>. Для этого рассмотрим следующую программу:
<tex>p'(x):</tex>
<tex>return (1 - p(x));</tex>
<tex>P(p'(x) = [x \in \overline{L}]) = P(p(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Таким образом <tex>\overline{L} \in \mathrm{BPP}</tex>.
#<tex>L \in \mathrm{BPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{coBPP}</tex>. Получаем <tex>\mathrm{BPP} \subset \mathrm{coBPP}</tex>.
#<tex>L \in \mathrm{coBPP} \Rightarrow \overline{L} \in \mathrm{BPP} \Rightarrow L = \overline{\overline{L}} \in \mathrm{BPP}</tex>. Получаем <tex>\mathrm{coBPP} \subset \mathrm{BPP}</tex>.
}}

==Теорема==
{{ Теорема
| about = Лаутеман
| statement = <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}</tex>
| proof =

Из того, что класс <tex>\mathrm{BPP}</tex> замкнут относительно дополнения и <tex>\mathrm{co\Sigma_2} = \mathrm{\Pi_2}</tex>, следует, что достаточно доказать включение <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2}</tex>.

<tex>\mathrm{BPP}</tex> можно определить как множество таких языков <tex>L</tex>, что <tex>x \in L</tex> тогда и только тогда, когда существует «много» таких вероятностных лент <tex>y</tex>, что <tex>M(x,y)</tex>, где <tex>M</tex> — [[Вероятностные вычисления. Вероятностная машина Тьюринга | вероятностная машина Тьюринга]] для <tex>L</tex>. <tex>\mathrm{\Sigma_2}</tex> — множество таких языков <tex>L</tex>, что <tex>x \in L</tex> тогда и только тогда, когда существует такой <tex>y</tex>, что для любого <tex>z</tex> <tex>R(x, y, z)</tex>. Таким образом, необходимо уметь записывать «существует много» с помощью кванторов <tex>\exists</tex>, <tex>\forall</tex>.

Рассмотрим язык <tex>G = \{0, 1\}^t</tex> для некоторого <tex>t</tex>. Определим операцию <tex>\oplus</tex> над словами из этого языка как побитовое исключающее или.

Назовем <tex>X</tex>, содержащееся в <tex>G</tex>, <tex>k</tex>-большим, если существует такой набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>, что <tex>\bigcup\limits_{i=1}^{k} g_i \oplus X = G</tex>. Иначе будем называть <tex>X</tex> — <tex>k</tex>-маленьким.

Если <tex>|X| < \frac{2^t}{k}</tex>, то <tex>X</tex> является <tex>k</tex>-маленьким (так как <tex>k</tex> копий <tex>X</tex> не смогут покрыть <tex>G</tex>). Найдем достаточное условие, при котором <tex>X</tex> является <tex>k</tex>-большим.

Воспользуемся утверждением, что если вероятность <tex>P(x \in A) > 0</tex>, то существует <tex>x</tex> из <tex>A</tex>. Для этого
выберем случайно набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>.

<tex>P(\bigcup\limits_{i=1}^{k} g_i \oplus X \not = G) = P(\exists y \not \in \bigcup\limits_{i=1}^{k} g_i \oplus X) = P(\bigvee\limits_{i=1}^{2^t} y_i \not \in \bigcup\limits_{j=1}^{k} g_j \oplus X)</tex> <tex>\leqslant 2^t P(y \not \in \bigcup\limits_{i=1}^{k} g_i \oplus X) = 2^t P(\bigwedge\limits_{i=1}^{k} y \oplus g_i \not \in X) = 2^t \left(P(y \not \in X)\right)^k = 2^t \left(1 - \frac{|X|}{2^t}\right)^k</tex>.

Если <tex>2^t\left(1 - \frac{|X|}{2^t}\right)^k < 1</tex>, то существует такой набор <tex>\{g_i\}_{i=1}^{k} \subset G</tex>, что <tex>\bigcup\limits_{i=1}^{k} g_i \oplus X = G</tex>, то есть <tex>X</tex> — <tex>k</tex>-большое.

Рассмотрим язык <tex>L \in \mathrm{BPP}</tex>. Тогда существует вероятностная машина Тьюринга <tex>m</tex>, такая что <tex>P(m(x) = [x \in L]) \geqslant \frac{2}{3}</tex>. Пусть <tex>m</tex> использует <tex>r(n)</tex> бит случайной ленты. По аналогии c [[Классы BPP и PP|доказательством]] <tex>\mathrm{BPP} = \mathrm{BPP_{strong}}</tex>, построим машину <tex>M</tex>, которая запускает <tex>m</tex> достаточное число раз, чтобы получить вероятность ошибки <tex>\frac{1}{2^{p(n)}}</tex>, где <tex>p(n)</tex> это некоторый полином, который будет определён позднее. Будет достаточно <tex>c p(n)^2</tex> запусков. Соответственно, <tex>M</tex> использует <tex>c r(n) p(n)^2</tex> бит случайной ленты, <tex>P(M(x) = [x \in L]) \geqslant 1 - \frac{1}{2^{p(n)}}</tex>.

Зафиксируем <tex>x</tex>. Возьмем <tex>G = \{0, 1\}^{r(n)}</tex>. Рассмотрим множество <tex>A_x = \{r \in G \bigm| M(x,r) = 1\}</tex>. Подберем теперь <tex>p(n)</tex> и <tex>k</tex> так, чтобы <tex>x \in L \Leftrightarrow A_x</tex> — <tex>k</tex>-большое.

Если <tex>x \in L</tex>, то <tex>P(M(x) = 1) = \frac{|A_x|}{2^{r(n)}} \geqslant 1 - \frac{1}{2^{p(n)}} \Rightarrow |A_x| \geqslant 2^{r(n)} \left( 1 - \frac{1}{2^{p(n)}} \right)</tex>. Значит <tex>2^{r(n)} \left( 1 - \frac{|A_x|}{2^{r(n)}} \right)^k \leqslant 2^{r(n) - kp(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-большим потребуем <tex>2^{r(n) - kp(n)} < 1</tex>.

Если <tex>x \not \in L</tex>, то <tex>P(M(x) = 1) = \frac{|A_x|}{2^{r(n)}} \leqslant \frac{1}{2^{p(n)}} \Rightarrow |A_x| \leqslant 2^{r(n) - p(n)}</tex>. Чтобы в этом случае <tex>A_x</tex> было бы <tex>k</tex>-маленьким потребуем <tex>2^{r(n) - p(n)} < \frac{2^{r(n)}}{k}</tex>.

Выберем <tex>p(n)</tex> так, чтобы <tex>\frac{r(n)}{p(n)} < 2^{p(n)} - 2</tex> и <tex>k = \lceil \frac{r(n)}{p(n)} \rceil + 1</tex>. Получаем <tex>\frac{r(n)}{p(n)} < k < 2^{p(n)}</tex>, то есть <tex>x \in L \Leftrightarrow A_x</tex> — <tex>k</tex>-большое.

Таким образом, <tex>x \in L \Leftrightarrow \exists \{g_i\}_{i=1}^{k} \subset G</tex> : <tex>\forall y \in G</tex> <tex>\left( \bigvee\limits_{i=1}^{k} y \in g_i \oplus A_x \right) </tex>. Заметив, что <tex>y \in g_i \oplus A_x \Leftrightarrow y \oplus g_i \in A_x \Leftrightarrow M(x, y \oplus g_i)</tex>, получаем <tex>L \in \Sigma_2</tex>, <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2}</tex> и <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}</tex>.
}}

== См. также ==
*[[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Классы PH, Σ и Π]]
*[[Классы BPPweak и BPPstrong]]

== Литература ==
* ''Sanjeev Arora, Boaz Barak''. [http://www.cs.princeton.edu/theory/complexity Computational Complexity: A Modern Approach]

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

Класс P

2012-06-04T16:16:33Z

Tsar: /* P-полные задачи */ Всё-таки, там ref выглядит страшно

== Определение ==
{{Определение
|definition=
'''Класс''' <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> устойчив и в обратном преобразовании модели вычислений.

== Свойства класса P ==
{{Теорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Примеры задач и языков из 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 =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}

{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \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 = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</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/>

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

Класс P

2012-06-04T16:10:32Z

Tsar: Мелкие правки

== Определение ==
{{Определение
|definition=
'''Класс''' <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> устойчив и в обратном преобразовании модели вычислений.

== Свойства класса P ==
{{Теорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Примеры задач и языков из 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 =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}

{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \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 = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</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/>

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

Класс P

2012-06-04T16:00:56Z

Tsar: /* P-полные задачи */ Дважды ссылка на одно и то же - перебор

== Определение ==
{{Определение
|definition=
'''Класс''' <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> устойчив и в обратном преобразовании модели вычислений.

== Свойства класса P ==
{{Теорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Примеры задач и языков из 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 =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}

{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \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 = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</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/>

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

Класс P

2012-06-04T15:57:32Z

Tsar: /* P-полные задачи */ Параметризуем общее определение вместо своего

== Определение ==
{{Определение
|definition=
'''Класс''' <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> устойчив и в обратном преобразовании модели вычислений.

== Свойства класса P ==
{{Теорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Примеры задач и языков из 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 =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}

{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \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 = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</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/>

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

Класс P

2012-06-04T15:48:25Z

Tsar: /* Устойчивость класса P к изменению модели вычислений */ Правки корявости

== Определение ==
{{Определение
|definition=
'''Класс''' <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> устойчив и в обратном преобразовании модели вычислений.

== Свойства класса P ==
{{Теорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Примеры задач и языков из 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 =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}

{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== P-полные задачи ==
{{Определение
|definition=
Язык <tex>X</tex> является <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полным]], если:
# <tex>X \in \mathrm{P}</tex>;
# <tex>\forall Y \in \mathrm{P} \Rightarrow Y \leq_L X</tex> (то есть любой язык из класса <tex>\mathrm{P}</tex> [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сводится]] к <tex>X</tex> с использованием <tex>O(log(n))</tex> памяти).
}}

{{Определение
|definition=
<tex>CIRCVAL = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</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/>

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

Класс P

2012-06-04T15:41:59Z

Tsar: Нечто про устойчивость

== Определение ==
{{Определение
|definition=
'''Класс''' <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> устойчив и в обратном преобразовании модели вычислений.

== Свойства класса P ==
{{Теорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Примеры задач и языков из 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 =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}

{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== P-полные задачи ==
{{Определение
|definition=
Язык <tex>X</tex> является <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полным]], если:
# <tex>X \in \mathrm{P}</tex>;
# <tex>\forall Y \in \mathrm{P} \Rightarrow Y \leq_L X</tex> (то есть любой язык из класса <tex>\mathrm{P}</tex> [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сводится]] к <tex>X</tex> с использованием <tex>O(log(n))</tex> памяти).
}}

{{Определение
|definition=
<tex>CIRCVAL = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</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/>

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

Класс P

2012-06-04T15:20:57Z

Tsar: Ссылка на сведение ещё одна

== Определение ==
{{Определение
|definition=
'''Класс''' <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 ==
{{Теорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Примеры задач и языков из 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 =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}

{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== P-полные задачи ==
{{Определение
|definition=
Язык <tex>X</tex> является <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полным]], если:
# <tex>X \in \mathrm{P}</tex>;
# <tex>\forall Y \in \mathrm{P} \Rightarrow Y \leq_L X</tex> (то есть любой язык из класса <tex>\mathrm{P}</tex> [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сводится]] к <tex>X</tex> с использованием <tex>O(log(n))</tex> памяти).
}}

{{Определение
|definition=
<tex>CIRCVAL = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</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/>

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

Класс P

2012-06-04T15:17:15Z

Tsar: Ссылка на книгу с доказательством P-полноты CIRCVAL

== Определение ==
{{Определение
|definition=
'''Класс''' <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 ==
{{Теорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Примеры задач и языков из 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 =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}

{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== P-полные задачи ==
{{Определение
|definition=
Язык <tex>X</tex> является <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полным]], если:
# <tex>X \in \mathrm{P}</tex>;
# <tex>\forall Y \in \mathrm{P} \Rightarrow Y \leq_L X</tex> (то есть любой язык из класса <tex>\mathrm{P}</tex> сводится к <tex>X</tex> с использованием <tex>O(log(n))</tex> памяти).
}}

{{Определение
|definition=
<tex>CIRCVAL = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</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/>

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

Класс P

2012-06-04T15:12:38Z

Tsar: /* Пример P-полной задачи */ Определение P-полноты, всё же

== Определение ==
{{Определение
|definition=
'''Класс''' <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 ==
{{Теорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Примеры задач и языков из 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 =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}

{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== P-полные задачи ==
{{Определение
|definition=
Язык <tex>X</tex> является <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полным]], если:
# <tex>X \in \mathrm{P}</tex>;
# <tex>\forall Y \in \mathrm{P} \Rightarrow Y \leq_L X</tex> (то есть любой язык из класса <tex>\mathrm{P}</tex> сводится к <tex>X</tex> с использованием <tex>O(log(n))</tex> памяти).
}}

{{Определение
|definition=
<tex>CIRCVAL = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</tex> это логическая схема.
}}

{{Теорема
|statement =
<tex>CIRCVAL</tex> {{---}} <tex>\mathrm{P}</tex>-полная задача.
}}

== Ссылки ==
<references/>

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

Класс P

2012-06-04T14:58:37Z

Tsar: Добавил что-то по пункту "7" из требований АС

== Определение ==
{{Определение
|definition=
'''Класс''' <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 ==
{{Теорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Примеры задач и языков из 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 =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}

{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

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

{{Теорема
|statement =
<tex>CIRCVAL</tex> {{---}} <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полная]] задача.
}}

== Ссылки ==
<references/>

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

Класс P

2012-06-04T14:22:30Z

Tsar: /* Примеры задач и языков из P */ Союз "и" нелеп

== Определение ==
{{Определение
|definition=
'''Класс''' <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 ==
{{Теорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Примеры задач и языков из 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 =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}

{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Ссылки ==
<references/>

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

Класс P

2012-06-04T14:21:22Z

Tsar: Склонение

== Определение ==
{{Определение
|definition=
'''Класс''' <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 ==
{{Теорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Примеры задач и языков из 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 =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}

{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Ссылки ==
<references/>

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

Класс P

2012-06-04T14:20:36Z

Tsar: Попытки что-то исправить (пункты от АС №3, 4, 5)

== Определение ==
{{Определение
|definition=
'''Класс''' <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 ==
{{Теорема
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Примеры задач и языков из 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 =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
}}

{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Ссылки ==
<references/>

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

Класс P

2012-06-04T10:49:44Z

Tsar: /* Свойства класса P */ Замена жаргонизма

== Определение ==
{{Определение
|definition=
'''Класс''' <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 ==
{{Лемма
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subseteq \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Понятно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
''Замечание.'' <tex>\mathrm{TS}</tex> {{---}} ограничение и по времени, и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>.

== Ссылки ==
<references/>

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

Класс P

2012-06-02T18:27:48Z

Tsar: /* Свойства класса P */ Попытки пояснить...

== Определение ==
{{Определение
|definition=
'''Класс''' <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 ==
{{Лемма
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Очевидно, что <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>L_1^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
''Замечание.'' <tex>\mathrm{TS}</tex> {{---}} ограничение и по времени, и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>.

== Ссылки ==
<references/>

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

Класс P

2012-06-02T18:07:29Z

Tsar: /* Свойства класса P */ Так. К ограничению сверху, наверное, нужны ещё пояснения

== Определение ==
{{Определение
|definition=
'''Класс''' <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 ==
{{Лемма
|statement =
Класс <tex>\mathrm{P}</tex> замкнут относительно [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведения по Карпу]]. <tex>L \in \mathrm{P}, M \le L \Rightarrow M \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 =
<tex>D \subset \mathrm{P} \Rightarrow \mathrm{P}=\mathrm{P}^D</tex>. В частности, из этого следует, что <tex>\mathrm{P}=\mathrm{P^P}</tex>.
|proof =
Очевидно, что <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>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>n = |w|</tex>
<tex>endPoses = \{0\}</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^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>.
}}

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg} \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg} \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>
''Замечание.'' <tex>\mathrm{TS}</tex> {{---}} ограничение и по времени, и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{CFL} \subset P</tex>.
|proof =
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>.

== Ссылки ==
<references/>

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

Класс P

2012-06-02T16:00:12Z

Tsar: /* Свойства класса P */ + mathrm

Класс P

2012-06-02T15:57:28Z

Tsar: /* Свойства класса P */ Тривиальное доказательство первого свойства

Класс P

2012-06-02T15:18:53Z

Tsar: /* Свойства класса P */ Разбиение свойств на 3 леммы, первые 2 ещё без доказательств

Обсуждение:Класс P

2012-05-06T10:03:54Z

Tsar: /* TODO 2 */ Всё сделал

== TODO ==
* Смысловая фигня:
** То, что вверху написано — это, насколько я понимаю, определение. Его надо перенести вниз, чтобы оно было после оглавления. Ещё там написана какая-то чушь. Что такое <tex>i</tex> в двойном определении, что такое вообще <tex>in</tex>?
*** Перенёс и поправил само определение. Лида написала там <tex>in</tex> когда-то, идейно это тоже верно, как мне кажется. Но теперь я уже занёс то определение, которое нам давал А.С.
** Определения надо НОРМАЛЬНО оформить. Как и для теорем, для них есть собственный шаблон.
*** Оформил.
** Ссылка на определение DTIME.
*** Очень долго думал, как её туда запилить... Так и не смог ничего разумного придумать. Нужен совет.
**** Я добавил ссылку. Не самый хороший костыль, конечно. Я ещё подумаю над этим.
** Что за <tex>L1</tex>. Проиндексируй нормально. А ещё там во второй строчке текст абсолютно сливается. Исправь.
*** Проиндексировал. А во второй строчке у меня всё в порядке... Либо я не понял, о чём ты.
**** Да, там всё теперь норм.
** Было бы неплохо написать хоть какие-нибудь идеи по поводу доказатеств свойств.
*** Свойство 1 кажется мне очевидным (если мы знаем тот факт, что сумма и произведение полиномов есть полином). Свойства 2 и 3 доказаны по ссылкам на соответствующие сведения (там есть конкретно рассмотрение этих сведений для задач из класса <tex>P</tex>).
**** Мне свойство 1 очевидным не кажется. Особенно какое-нибудь замыкание Клини. Но это несложные факты, поэтому я не прошу полное доказательство.
***** Написал довольно строгое доказательство замкнутости замыкания Клини. Остальные очень простые, смысла их расписывать не вижу.
** Ссылка на определение констекстно-свободных языков в формулировке соответствующей теоремы.
*** Сделал. Заодно и на регулярные языки тоже сделал ссылку.
** «Легко показать, что, по определению…» → «Легко показать, что, по определению <tex>P</tex>…»
*** Ок. Сделал.
* Остальная фигня:
** В первом определении после «то есть» двоеточие.
*** Хорошо, сделал.
** «Но, по теореме…» Запятая здесь не нужна. Мне кажется, лучше просто выпилить это «но».
*** Согласен, сделал.

== TODO 2 ==
* В перечислениях в конце каждого пункта ставится либо точка (если пункт — отдельное предложение), либо точка с запятой (если все пункты — это одно баааальшое предложение). Это я про интерпретацию определния <tex>P</tex>.
** Fixed.
* У доказательства замкнутости относительно замыкания Клини проблемы с форматированием: начало имеет отступ в «2 таба», а конец — вообще не имеет отступа. Думаю, что лучше это доказательство выделить в отделиную лемму и оформить соответствующе.
** Done.
* Будем считать, что мы научились ставить ссылки для текста в техе («примечаниями»). Поэтому в предпоследнем абзаце <tex>NP</tex> можно тоже написать нормально в техе.
** Fixed.
* Вставь ссылки на МТ и НМТ. МТ у нас в вики нет, так что эта ссылка — на википедию. Определние НМТ у нас есть.
** Done.

Класс P

2012-05-06T10:02:03Z

Tsar: /* Задача равенства P и NP */ Ааааа, вот как ссылка пилится норм

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

Итого, язык <tex>L</tex> лежит в классе <tex>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> L \in P , M \le L \Rightarrow M \in P</tex>.
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).

{{Лемма
|statement =
Если <tex>L \in P</tex>, то <tex>L^* \in P</tex>.
|proof =
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in P</tex>.
}}

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

== Задача равенства P и NP ==
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[NP]]</ref>, не разрешенный по сей день.

Легко показать, что, по определению <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>.

== Ссылки ==
<references/>

Класс P

2012-05-06T10:00:32Z

Tsar: /* Задача равенства P и NP */ Ссылка на ДМТ и НМТ

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

Итого, язык <tex>L</tex> лежит в классе <tex>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> L \in P , M \le L \Rightarrow M \in P</tex>.
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).

{{Лемма
|statement =
Если <tex>L \in P</tex>, то <tex>L^* \in P</tex>.
|proof =
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in P</tex>.
}}

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

== Задача равенства P и NP ==
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[NP]]</ref>, не разрешенный по сей день.

Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая ДМТ<ref>[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]</ref>, которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</tex>.

== Ссылки ==
<references/>

Класс P

2012-05-06T09:55:16Z

Tsar: NP в tex'е и ref

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

Итого, язык <tex>L</tex> лежит в классе <tex>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> L \in P , M \le L \Rightarrow M \in P</tex>.
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).

{{Лемма
|statement =
Если <tex>L \in P</tex>, то <tex>L^* \in P</tex>.
|proof =
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in P</tex>.
}}

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

== Задача равенства P и NP ==
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[NP]]</ref>, не разрешенный по сей день.

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

== Ссылки ==
<references/>

Класс P

2012-05-06T09:53:33Z

Tsar: /* Свойства класса P */ Упихал доказательство в отдельную лемму

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

Итого, язык <tex>L</tex> лежит в классе <tex>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> L \in P , M \le L \Rightarrow M \in P</tex>.
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>. Рассмотрим доказательство замкнутости замыкания Клини (остальные доказательства строятся аналогично).

{{Лемма
|statement =
Если <tex>L \in P</tex>, то <tex>L^* \in P</tex>.
|proof =
Пусть <tex>p</tex> {{---}} разрешитель <tex>L</tex>, работающий за полиномиальное время. Построим разрешитель <tex>q</tex> для языка <tex>L^*</tex>.
<tex>q(w):</tex>
<tex>n = |w|</tex>
<tex>endPoses = \{0\}</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^2 O(p(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за <tex>O(1)</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L^* \in P</tex>.
}}

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Класс P

2012-05-06T09:41:06Z

Tsar: /* Определение */ "В перечислениях в конце каждого пункта ставится либо точка, либо точка с запятой"

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

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

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Класс P

2012-05-02T14:37:06Z

Tsar: /* Свойства класса P */ Точка.

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

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

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Класс P

2012-05-02T14:31:41Z

Tsar: /* Свойства класса P */ Улучшаем асимптотику

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

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

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Обсуждение:Класс P

2012-05-02T14:27:44Z

Tsar: "Написал довольно строгое доказательство замкнутости замыкания Клини. Остальные очень простые, смысла их расписывать не вижу."

Класс P

2012-05-02T14:24:39Z

Tsar: /* Свойства класса P */ Поправочка худшей оценки

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

Итого, язык <tex>L</tex> лежит в классе <tex>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> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</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>n = |w|</tex>
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L_1</tex>
for (<tex>i = 1 \ldots n</tex>)
for (<tex>j \in endPoses</tex>)
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
Худшая оценка времени работы разрешителя <tex>q</tex> равна <tex>n^2 log(n) O(p_1(w))</tex>, так как в множестве <tex>endPoses</tex> может быть максимум <tex>n</tex> элементов, значит итерироваться по множеству можно за <tex>n</tex>, если реализовать его на основе дерева; при этом операция добавления элемента в множество будет работать за <tex>O(log(n))</tex>. Итого, разрешитель <tex>q</tex> работает за полиномиальное время (так как произведение полиномов есть полином). Значит <tex>L_1^* \in P</tex>.

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Класс P

2012-05-02T14:15:02Z

Tsar: /* Свойства класса P */ Теперь чёткое доказательство замкнутости замыкания Клини

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

Итого, язык <tex>L</tex> лежит в классе <tex>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> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</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>n = |w|</tex>
<tex>endPoses = \{0\}</tex> //позиции, где могут заканчиваться слова, принадлежащие <tex>L_1</tex>
for (<tex>i = 1 \ldots n</tex>)
for (<tex>j \in endPoses</tex>)
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
Худшая оценка времени работы разрешителя <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 ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Класс P

2012-04-30T18:48:19Z

Tsar: /* Свойства класса P */

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

Итого, язык <tex>L</tex> лежит в классе <tex>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> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</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>
if (|w| = 0)
return true
for (<tex>i = 1 \ldots |w|</tex>)
if (<tex>p_1(w[1..i])</tex> and <tex>q(w[i + 1..|w|])</tex>)
return true
return false
Мне кажется, он за полином работает. Завтра формально напишу, почему (если смогу).

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Обсуждение:Класс P

2012-04-30T08:35:06Z

Tsar: Последний ответ проверяющему

Обсуждение:Класс P

2012-04-30T08:29:30Z

Tsar: Ответы проверяющему (кроме одного)

Класс P

2012-04-30T08:24:43Z

Tsar: /* Задача равенства P и NP */ По определению P, а не просто по какому-то там

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

Итого, язык <tex>L</tex> лежит в классе <tex>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>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>.
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Класс P

2012-04-30T08:22:38Z

Tsar: + ссылки

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

Итого, язык <tex>L</tex> лежит в классе <tex>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>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>.
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Класс P

2012-04-30T08:19:12Z

Tsar: /* Определение */ Забытые теги <tex></tex>

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

Итого, язык <tex>L</tex> лежит в классе <tex>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>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>.
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс регулярных языков входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс контекстно-свободных языков входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Класс P

2012-04-30T08:18:02Z

Tsar: /* Свойства класса P */ Чиню ошибки форматирования

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

Итого, язык L лежит в классе <tex>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>L_1, L_2 \in P</tex>, то: <tex>L_1 \cup L_2 \in P</tex>, <tex>L_1 \cap L_2 \in P</tex>, <tex>L_1 L_2 \in P</tex>, <tex>L_1^* \in P</tex> и <tex>\overline{L_1} \in P</tex>.
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс регулярных языков входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс контекстно-свободных языков входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Класс P

2012-04-30T08:14:53Z

Tsar: /* Определение */ Теперь, мне кажется, что логично написать сюда слово "Итого"

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

Итого, язык L лежит в классе <tex>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>L_1, L_2 \in P</tex>, то: <tex>L1 \cup L2 \in P</tex>, <tex>L1 \cap L2 \in P</tex>, <tex>L1L2 \in P</tex>, <tex>L1^* \in P</tex> и <tex>\overline{L1} \in P</tex>.
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс регулярных языков входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс контекстно-свободных языков входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Класс P

2012-04-30T08:07:19Z

Tsar: Определение в нужное место; "Но, " - нафиг

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

Язык L лежит в классе <tex>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>L_1, L_2 \in P</tex>, то: <tex>L1 \cup L2 \in P</tex>, <tex>L1 \cap L2 \in P</tex>, <tex>L1L2 \in P</tex>, <tex>L1^* \in P</tex> и <tex>\overline{L1} \in P</tex>.
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс регулярных языков входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс контекстно-свободных языков входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Класс P

2012-04-16T18:43:20Z

Tsar: Может это моё личное мнение, но заголовки с tex-ом выглядят ужасно, к тому же из содержания tex-овские куски выпадают

'''Класс''' <tex>P</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть

<tex>P=\bigcup\limits_{i=0}^{\infty} DTIME(in^i)=\bigcup\limits_{i=0}^{\infty}\bigcup\limits_{k=0}^{\infty} DTIME(in^k)</tex>.

== Определение ==
Язык L лежит в классе <tex>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>L_1, L_2 \in P</tex>, то: <tex>L1 \cup L2 \in P</tex>, <tex>L1 \cap L2 \in P</tex>, <tex>L1L2 \in P</tex>, <tex>L1^* \in P</tex> и <tex>\overline{L1} \in P</tex>.
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.

== Соотношение классов Reg и P ==
{{Теорема
|statement =
Класс регулярных языков входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов CFL и P ==
{{Теорема
|statement =
Класс контекстно-свободных языков входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из 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>P</tex>.

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

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

== Ссылки ==
<references/>

Класс P

2012-04-16T18:31:02Z

Tsar: /* Примеры задач и языков из P */ + упоминание ещё одной задачи

'''Класс''' <tex>P</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть

<tex>P=\bigcup\limits_{i=0}^{\infty} DTIME(in^i)=\bigcup\limits_{i=0}^{\infty}\bigcup\limits_{k=0}^{\infty} DTIME(in^k)</tex>.

== Определение ==
Язык L лежит в классе <tex>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>, то она не допустит его

== Свойства класса <tex>P</tex> ==
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L1 \cup L2 \in P</tex>, <tex>L1 \cap L2 \in P</tex>, <tex>L1L2 \in P</tex>, <tex>L1^* \in P</tex> и <tex>\overline{L1} \in P</tex>.
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.

== Соотношение классов <tex>Reg</tex> и <tex>P</tex> ==
{{Теорема
|statement =
Класс регулярных языков входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов <tex>CFL</tex> и <tex>P</tex> ==
{{Теорема
|statement =
Класс контекстно-свободных языков входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из <tex>P</tex> ==
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
* определение связности графов;
* вычисление наибольшего общего делителя;
* задача линейного программирования;
* проверка простоты числа.<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>.

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

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

== Ссылки ==
<references/>

Класс P

2012-04-16T18:29:37Z

Tsar: Точки

'''Класс''' <tex>P</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть

<tex>P=\bigcup\limits_{i=0}^{\infty} DTIME(in^i)=\bigcup\limits_{i=0}^{\infty}\bigcup\limits_{k=0}^{\infty} DTIME(in^k)</tex>.

== Определение ==
Язык L лежит в классе <tex>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>, то она не допустит его

== Свойства класса <tex>P</tex> ==
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L1 \cup L2 \in P</tex>, <tex>L1 \cap L2 \in P</tex>, <tex>L1L2 \in P</tex>, <tex>L1^* \in P</tex> и <tex>\overline{L1} \in P</tex>.
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.

== Соотношение классов <tex>Reg</tex> и <tex>P</tex> ==
{{Теорема
|statement =
Класс регулярных языков входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов <tex>CFL</tex> и <tex>P</tex> ==
{{Теорема
|statement =
Класс контекстно-свободных языков входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из <tex>P</tex> ==
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
* определение связности графов;
* вычисление наибольшего общего делителя.
* проверка простоты числа.<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>.

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

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

== Ссылки ==
<references/>

Класс P

2012-04-16T18:28:44Z

Tsar: + ещё теоремка

'''Класс''' <tex>P</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть

<tex>P=\bigcup\limits_{i=0}^{\infty} DTIME(in^i)=\bigcup\limits_{i=0}^{\infty}\bigcup\limits_{k=0}^{\infty} DTIME(in^k)</tex>.

== Определение ==
Язык L лежит в классе <tex>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>, то она не допустит его

== Свойства класса <tex>P</tex> ==
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L1 \cup L2 \in P</tex>, <tex>L1 \cap L2 \in P</tex>, <tex>L1L2 \in P</tex>, <tex>L1^* \in P</tex> и <tex>\overline{L1} \in P</tex>.
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.

== Соотношение классов <tex>Reg</tex> и <tex>P</tex> ==
{{Теорема
|statement =
Класс регулярных языков входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Соотношение классов <tex>CFL</tex> и <tex>P</tex> ==
{{Теорема
|statement =
Класс контекстно-свободных языков входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}

== Примеры задач и языков из <tex>P</tex> ==
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
* определение связности графов;
* вычисление наибольшего общего делителя.
* проверка простоты числа.<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>.

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

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

== Ссылки ==
<references/>

Класс P

2012-04-16T18:11:49Z

Tsar: + теоремка

'''Класс''' <tex>P</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть

<tex>P=\bigcup\limits_{i=0}^{\infty} DTIME(in^i)=\bigcup\limits_{i=0}^{\infty}\bigcup\limits_{k=0}^{\infty} DTIME(in^k)</tex>.

== Определение ==
Язык L лежит в классе <tex>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>, то она не допустит его

== Свойства класса <tex>P</tex> ==
# Замкнутость объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если <tex>L_1, L_2 \in P</tex>, то: <tex>L1 \cup L2 \in P</tex>, <tex>L1 \cap L2 \in P</tex>, <tex>L1L2 \in P</tex>, <tex>L1^* \in P</tex> и <tex>\overline{L1} \in P</tex>.
# Замкнутость относительно [[Сведение по Карпу|сведения по Карпу]]. <tex> L \in P , M \le L \Rightarrow M \in P</tex>
# Замкнутость относительно [[Сведение по Куку|сведения по Куку]]. <tex>L \subset P \Rightarrow P=P^L</tex>.

== Соотношение классов <tex>Reg</tex> и <tex>P</tex> ==
{{Теорема
|statement =
<tex>Reg \subset P</tex>
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}

== Примеры задач и языков из <tex>P</tex> ==
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
* определение связности графов;
* вычисление наибольшего общего делителя.
* проверка простоты числа.<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>.

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

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

== Ссылки ==
<references/>