PCP-система - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:35:42Z

rollbackEdits.php mass rollback

185.220.100.254 в 04:13, 1 сентября 2022

2022-09-01T04:13:39Z

188.243.10.149: /* Свойства */

2017-02-12T10:38:31Z

‎Свойства

95.55.113.66: /* Свойства */

2015-06-11T13:51:15Z

‎Свойства

95.55.113.66: /* Свойства */

2015-06-10T19:42:28Z

‎Свойства

Filchenko: /* Свойства */ PCP теорема, анонс

2012-06-06T18:41:42Z

‎Свойства: PCP теорема, анонс

194.85.161.34 в 11:42, 5 июня 2012

2012-06-05T11:42:07Z

194.85.161.34 в 11:40, 5 июня 2012

2012-06-05T11:40:11Z

Логунов Глеб в 23:09, 4 июня 2012

2012-06-04T23:09:10Z

Логунов Глеб в 23:05, 4 июня 2012

2012-06-04T23:05:47Z

← Предыдущая		Версия 16:35, 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 Майкл Наки].
−	\|}
−
	[[Категория: Теория сложности]]		[[Категория: Теория сложности]]
	'''PCP(probabilistically checkable proof)''' - вид доказательства, проверяемого рандомизированным алгоритмом, использующим ограниченное число случайных бит и читающим ограниченное число бит доказательства. Такой алгоритм должен с достаточно высокими вероятностями принимать корректные доказательства и отвергать ошибочные.		'''PCP(probabilistically checkable proof)''' - вид доказательства, проверяемого рандомизированным алгоритмом, использующим ограниченное число случайных бит и читающим ограниченное число бит доказательства. Такой алгоритм должен с достаточно высокими вероятностями принимать корректные доказательства и отвергать ошибочные.

← Предыдущая		Версия 04:13, 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 Майкл Наки].
		+	\|}
		+
	[[Категория: Теория сложности]]		[[Категория: Теория сложности]]
	'''PCP(probabilistically checkable proof)''' - вид доказательства, проверяемого рандомизированным алгоритмом, использующим ограниченное число случайных бит и читающим ограниченное число бит доказательства. Такой алгоритм должен с достаточно высокими вероятностями принимать корректные доказательства и отвергать ошибочные.		'''PCP(probabilistically checkable proof)''' - вид доказательства, проверяемого рандомизированным алгоритмом, использующим ограниченное число случайных бит и читающим ограниченное число бит доказательства. Такой алгоритм должен с достаточно высокими вероятностями принимать корректные доказательства и отвергать ошибочные.

@@ Строка 38: / Строка 38: @@
 |statement = <tex>\mathrm{PCP}[poly(n), 0]</tex> = <tex>\mathrm{coRP}</tex>.
 |proof =
-Очевидно следует из [[Вероятностные вычисления. Вероятностная машина Тьюринга#Вероятностные сложностные классы|определения coRP]].
+Очевидно следует из [[Классы RP и coRP#Определения|определения coRP]].
 }}
 {{Теорема

@@ Строка 38: / Строка 38: @@
 |statement = <tex>\mathrm{PCP}[poly(n), 0]</tex> = <tex>\mathrm{coRP}</tex>.
 |proof =
 Очевидно следует из [[Вероятностные вычисления. Вероятностная машина Тьюринга#Вероятностные сложностные классы|определения coRP]].
 }}

@@ Строка 38: / Строка 38: @@
 |statement = <tex>\mathrm{PCP}[poly(n), 0]</tex> = <tex>\mathrm{coRP}</tex>.
 |proof =
 Очевидно следует из [[Вероятностные вычисления. Вероятностная машина Тьюринга#Вероятностные сложностные классы|определения coRP]].
 }}

@@ Строка 44: / Строка 44: @@
 |proof =
 Очевидно следует из [[Классы_NP_и_Σ₁|определения Σ₁]].
 }}

@@ Строка 29: / Строка 29: @@
 == Свойства ==
 {{Теорема
-|statement = <tex>\mathrm{PCP}[0, 0]</tex> = <tex>\mathrm{PCP}[O(log(n)), 0]</tex> = <tex>\mathrm{PCP}[0, O(log(n))]</tex> = <tex>\mathrm{P}</tex>.
+|statement = <tex>\mathrm{PCP}[0, 0]</tex> = <tex>\mathrm{PCP}[O(\log(n)), 0]</tex> = <tex>\mathrm{PCP}[0, O(\log(n))]</tex> = <tex>\mathrm{P}</tex>.
 |proof =
 * <tex>\mathrm{PCP}[0, 0]</tex> = <tex>\mathrm{P}</tex>: вероятностная МТ не использует случайные биты и не обращается к доказательству, то есть работает как детерминированная МТ, работающая за полиномиальное время.

@@ Строка 32: / Строка 32: @@
 |proof =
 * <tex>\mathrm{PCP}[0, 0]</tex> = <tex>\mathrm{P}</tex>: вероятностная МТ не использует случайные биты и не обращается к доказательству, то есть работает как детерминированная МТ, работающая за полиномиальное время.
-* <tex>\mathrm{PCP}[O(log(n)), 0]</tex> = <tex>\mathrm{P}</tex>: доступ к <tex>O(log(n))</tex> случайных бит не меняет ситуации, так как все возможные битовые цепочки логарифмической длины детерминированная МТ может сгенерировать и проверить за полиномиальное время.
+* <tex>\mathrm{PCP}[O(\log(n)), 0]</tex> = <tex>\mathrm{P}</tex>: доступ к <tex>O(\log(n))</tex> случайных бит не меняет ситуации, так как все возможные битовые цепочки логарифмической длины детерминированная МТ может сгенерировать и проверить за полиномиальное время.
-* <tex>\mathrm{PCP}[0, O(log(n))]</tex> = <tex>\mathrm{P}</tex>: так как доступа к случайным битам нет, <tex>\pi</tex> можно рассматривать как битовую цепочку логарифмической длины. Все возможные такие цепочки детерминированная МТ может сгенерировать и проверить за полиномиальное время.
+* <tex>\mathrm{PCP}[0, O(\log(n))]</tex> = <tex>\mathrm{P}</tex>: так как доступа к случайным битам нет, <tex>\pi</tex> можно рассматривать как битовую цепочку логарифмической длины. Все возможные такие цепочки детерминированная МТ может сгенерировать и проверить за полиномиальное время.
 }}
 {{Теорема

@@ Строка 24: / Строка 24: @@
 |definition =
 Сложностный класс <tex>\mathrm{PCP}_{c(n), s(n)}[r(n), q(n)]</tex> {{---}} это объединение всех языков, для которых существует <tex>\mathrm{PCP}</tex>-система над бинарным алфавитом с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex>, в которой неадаптивный верификатор <tex>V</tex> работает за полиномиальное время и имеет вероятностную и запросную сложности соответственно <tex>r(n)</tex> и <tex>q(n)</tex>, а доказательства имеют экспоненциальную длину.<br/>
-Часто <tex>\mathrm{PCP}_{1, {}^1/{}_2}[r(n), q(n)]</tex> обозначают как <tex>\mathrm{PCP}[r(n), q(n)]</tex>.
+Часто <tex>\mathrm{PCP}_{1, \frac{1}{2}}[r(n), q(n)]</tex> обозначают как <tex>\mathrm{PCP}[r(n), q(n)]</tex>.
 }}
@@ Строка 69: / Строка 69: @@
 Проверим полноту и обоснованность:
 * '''Полнота''': если графы неизоморфны, то существует <tex>\pi</tex> такая, что всякий её символ равен 1 или 2 и задан корректно. Тогда на этой <tex>\pi</tex> верификатор всегда вернёт 1;
-* '''Обоснованность''': если графы изоморфны, то фиксируем <tex>\pi</tex>. Пусть <tex>\Omega</tex> {{---}} это множество всех конфигураций случайной ленты, с которой работает <tex>V</tex>. Заметим, что все конфигурации из <tex>\Omega</tex> будут переданы <tex>V</tex> с равными вероятностями. Теперь рассмотрим произвольную конфигурацию типа <tex>\psi</tex> из <tex>\Omega</tex>, то есть конфигурацию, на которой <tex>V</tex> допускает <tex>\langle G_1, G_2 \rangle</tex>. Заметим, что для каждой такой конфигурации существует однозначно определяемая конфигурация типа <tex>\overline \psi</tex>, отличающаяся от <tex>\psi</tex> только первым битом и также принадлежащая <tex>\Omega</tex>. Запустившись на <tex>\overline \psi</tex>, <tex>V</tex>, очевидно, отвергнет <tex>\langle G_1, G_2 \rangle</tex>. Таким образом, конфигураций типа <tex>\psi</tex> в <tex>\Omega</tex> не больше половины. Как уже отмечалось, конфигурации из <tex>\Omega</tex> подаются <tex>V</tex> с равными вероятностями, а конфигураций не из <tex>\Omega</tex>, по определению, <tex>V</tex> не подаётся. Таким образом, вероятность ошибки не превышает <tex>{}^1/{}_2</tex>.
+* '''Обоснованность''': если графы изоморфны, то фиксируем <tex>\pi</tex>. Пусть <tex>\Omega</tex> {{---}} это множество всех конфигураций случайной ленты, с которой работает <tex>V</tex>. Заметим, что все конфигурации из <tex>\Omega</tex> будут переданы <tex>V</tex> с равными вероятностями. Теперь рассмотрим произвольную конфигурацию типа <tex>\psi</tex> из <tex>\Omega</tex>, то есть конфигурацию, на которой <tex>V</tex> допускает <tex>\langle G_1, G_2 \rangle</tex>. Заметим, что для каждой такой конфигурации существует однозначно определяемая конфигурация типа <tex>\overline \psi</tex>, отличающаяся от <tex>\psi</tex> только первым битом и также принадлежащая <tex>\Omega</tex>. Запустившись на <tex>\overline \psi</tex>, <tex>V</tex>, очевидно, отвергнет <tex>\langle G_1, G_2 \rangle</tex>. Таким образом, конфигураций типа <tex>\psi</tex> в <tex>\Omega</tex> не больше половины. Как уже отмечалось, конфигурации из <tex>\Omega</tex> подаются <tex>V</tex> с равными вероятностями, а конфигураций не из <tex>\Omega</tex>, по определению, <tex>V</tex> не подаётся. Таким образом, вероятность ошибки не превышает <tex>\frac{1}{2}</tex>.
 }}

@@ Строка 5: / Строка 5: @@
 {{Определение
 |definition =
-<tex>\mathrm{PCP}</tex>'''-системой''' (системой вероятностно проверяемых доказательств) с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex> над алфавитом <tex>\Sigma</tex> для языка <tex>L</tex>, где <tex>0 \le s(n) \le c(n) \le 1</tex>, называется <tex>V</tex> {{---}} [[Вероятностные вычисления. Вероятностная машина Тьюринга#Основные определения|вероятностная машина Тьюринга]], имеющая доступ к доказательству <tex>\pi</tex> {{---}} цепочке из <tex>\Sigma^{*}</tex>, удовлетворяющая следующим свойствам:
+<tex>\mathrm{PCP}</tex>'''-системой''' (системой вероятностно проверяемых доказательств) с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex> над алфавитом <tex>\Sigma</tex> для языка <tex>L</tex>, где <tex>0 \le s(n) \le c(n) \le 1</tex>, называется верификатор <tex>V</tex> {{---}} [[Вероятностные вычисления. Вероятностная машина Тьюринга#Основные определения|вероятностная машина Тьюринга]], имеющая доступ к доказательству <tex>\pi</tex> {{---}} цепочке из <tex>\Sigma^{*}</tex>, удовлетворяющая следующим свойствам:
 * '''Полнота''': если <tex>x \in L</tex>, то вероятность того, что <tex>V^{\pi}</tex> допустит <tex>x</tex>, не меньше <tex>c(n)</tex> для некоторого <tex>\pi</tex>,
 * '''Обоснованность''': если <tex>x \notin L</tex>, то вероятность того, что <tex>V^{\pi}</tex> допустит <tex>x</tex>, не больше <tex>s(n)</tex> для любого <tex>\pi</tex>.