Класс P - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:18:22Z

rollbackEdits.php mass rollback

171.25.193.80 в 05:33, 1 сентября 2022

2022-09-01T05:33:00Z

Infovarius в 13:02, 14 ноября 2018

2018-11-14T13:02:58Z

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

2012-06-04T16:16:33Z

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

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

2012-06-04T16:10:32Z

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

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

2012-06-04T16:00:56Z

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

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

2012-06-04T15:57:32Z

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

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

2012-06-04T15:48:25Z

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

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

2012-06-04T15:41:59Z

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

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

2012-06-04T15:20:57Z

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

← Предыдущая		Версия 16:18, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	== Определение ==		== Определение ==
	{{Определение		{{Определение

← Предыдущая		Версия 05:33, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	== Определение ==		== Определение ==
	{{Определение		{{Определение

← Предыдущая		Версия 13:02, 14 ноября 2018
Строка 109:		Строка 109:
	<references/>		<references/>

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

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

@@ Строка 12: / Строка 12: @@
 == Устойчивость класса P к изменению модели вычислений ==
-Машина Тьюринга может симулировать другие модели вычислений (например, языки программирования) с не более чем полиномиальным замедлением. Благодаря этому, класс <tex>\mathrm{P}</tex> на этих моделях не становится больше.
+Машина Тьюринга может симулировать другие модели вычислений (например, языки программирования) с не более чем полиномиальным замедлением. Благодаря этому, класс <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> устойчив и в обратном преобразовании модели вычислений.
@@ Строка 94: / Строка 94: @@
 == P-полные задачи ==
-Говоря про <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полноту]], мы, как правило, подразумеваем <tex>\mathrm{P}</tex>-полноту относительно <tex>\widetilde{\mathrm{L}}</tex>-сведения.<ref>[[Классы L, NL, coNL. NL-полнота задачи о достижимости]]</ref>
+Говоря про <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полноту]], мы, как правило, подразумеваем <tex>\mathrm{P}</tex>-полноту относительно <tex>\widetilde{\mathrm{L}}</tex><ref>[[Классы L, NL, coNL. NL-полнота задачи о достижимости]]</ref>-сведения.
 {{Определение

@@ Строка 10: / Строка 10: @@
 # если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;
 # если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.
 == Свойства класса P ==

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