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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:25:14Z

rollbackEdits.php mass rollback

103.251.167.21 в 04:55, 1 сентября 2022

2022-09-01T04:55:25Z

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

2010-06-18T12:23:55Z

‎Свойства

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

2010-06-18T12:21:17Z

‎Свойства

192.168.0.2: /* Определение */

2010-06-16T19:54:44Z

‎Определение

192.168.0.2 в 08:53, 3 июня 2010

2010-06-03T08:53:02Z

192.168.0.2 в 08:51, 3 июня 2010

2010-06-03T08:51:33Z

192.168.0.2: /* Определение */

2010-06-03T08:19:18Z

‎Определение

192.168.0.2 в 18:01, 1 июня 2010

2010-06-01T18:01:05Z

Joshik в 12:42, 1 июня 2010

2010-06-01T12:42:54Z

← Предыдущая		Версия 16:25, 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[r(n), q(n)]''' ('''PCP''' - Probabilistically Checkable Proof), где <tex>n</tex> - длина входного слова, называется множество языков, распознаваемых машиной <tex>V^{\pi}(x)</tex>, обладающей следующими свойствами:		Классом '''PCP[r(n), q(n)]''' ('''PCP''' - Probabilistically Checkable Proof), где <tex>n</tex> - длина входного слова, называется множество языков, распознаваемых машиной <tex>V^{\pi}(x)</tex>, обладающей следующими свойствами:

← Предыдущая		Версия 04:55, 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[r(n), q(n)]''' ('''PCP''' - Probabilistically Checkable Proof), где <tex>n</tex> - длина входного слова, называется множество языков, распознаваемых машиной <tex>V^{\pi}(x)</tex>, обладающей следующими свойствами:		Классом '''PCP[r(n), q(n)]''' ('''PCP''' - Probabilistically Checkable Proof), где <tex>n</tex> - длина входного слова, называется множество языков, распознаваемых машиной <tex>V^{\pi}(x)</tex>, обладающей следующими свойствами:

@@ Строка 13: / Строка 13: @@
 ==Свойства==
-# '''PCP[0, 0] = [[P|P]]''' (по определению '''P''' - нет случайности и обращений к <tex>\pi</tex>)
+# '''PCP'''[0, 0] = '''[[P]]''' (по определению '''P''' - нет случайности и обращений к <tex>\pi</tex>)
-# '''PCP[log(n), 0] = [[P]]''' (логарифмическое число обращений к случайной ленте не помогают, так как можно за полиномиальное время перебрать всевозможные результаты обращений)
+# '''PCP'''[''log(n)'', 0] = '''P''' (логарифмическое число обращений к случайной ленте не помогают, так как можно за полиномиальное время перебрать всевозможные результаты обращений)
-# '''PCP[0, log(n)] = [[P]]''' (логарифмическое число обращений к строке <tex>\pi</tex> также не помогают, так как можно аналогичным образом перебрать всевозможные результаты обращений за полиномиальное время)
+# '''PCP'''[0, ''log(n)''] = '''P''' (логарифмическое число обращений к строке <tex>\pi</tex> также не помогают, так как можно аналогичным образом перебрать всевозможные результаты обращений за полиномиальное время)
-# '''PCP[poly(n), 0] = [[Сложностные_классы_RP_и_coRP|co-RP]]''' (по определению '''coRP''')
+# '''PCP'''[''poly(n)'', 0] = '''[[Сложностные_классы_RP_и_coRP|co-RP]]''' (по определению '''co-RP''')
-# '''PCP[0, poly(n)] = [[NP|NP]]''' (по определению '''NP''' на языке сертификатов)
+# '''PCP'''[0, ''poly(n)''] = '''[[NP]]''' (по определению '''NP''' на языке сертификатов)
-# '''PCP[log(n), O(1)] = [[NP]]''' ([[PCP-теорема]])
+# '''PCP'''[''log(n)'', ''O''(1)] = '''NP''' ([[PCP-теорема]])
 ==Пример==

@@ Строка 14: / Строка 14: @@
 # '''PCP[0, 0] = [[P|P]]''' (по определению '''P''' - нет случайности и обращений к <tex>\pi</tex>)
-# '''PCP[log(n), 0] = [[P|P]]''' (логарифмическое число обращений к случайной ленте не помогают, так как можно за полиномиальное время перебрать всевозможные результаты обращений)
+# '''PCP[log(n), 0] = [[P]]''' (логарифмическое число обращений к случайной ленте не помогают, так как можно за полиномиальное время перебрать всевозможные результаты обращений)
-# '''PCP[0, log(n)] = [[P|P]]''' (логарифмическое число обращений к строке <tex>\pi</tex> также не помогают, так как можно аналогичным образом перебрать всевозможные результаты обращений за полиномиальное время)
+# '''PCP[0, log(n)] = [[P]]''' (логарифмическое число обращений к строке <tex>\pi</tex> также не помогают, так как можно аналогичным образом перебрать всевозможные результаты обращений за полиномиальное время)
-# '''PCP[poly(n), 0] = [[Сложностные_классы_RP_и_coRP|coRP]]''' (по определению '''coRP''')
+# '''PCP[poly(n), 0] = [[Сложностные_классы_RP_и_coRP|co-RP]]''' (по определению '''coRP''')
 # '''PCP[0, poly(n)] = [[NP|NP]]''' (по определению '''NP''' на языке сертификатов)
-# '''PCP[log(n), O(1)] = [[NP|NP]]''' ([[PCP-теорема]])
+# '''PCP[log(n), O(1)] = [[NP]]''' ([[PCP-теорема]])
 ==Пример==

@@ Строка 9: / Строка 9: @@
 # <tex>\  x \notin L \Rightarrow \forall \pi : Pr(V^{\pi}(x)=1)\le \frac{1}{2} </tex>.
-Можно считать, что строка <tex>\pi</tex> всегда такая, что пытается убедить <tex>V</tex> с максимальной вероятностью принять <tex>x</tex>. Если <tex>x \in L </tex>, то это происходить с вероятностью 1, иначе с вероятностью не более <tex> \frac{1}{2} </tex>.
+Можно считать, что строка <tex>\pi</tex> всегда такая, что пытается убедить <tex>V</tex> с максимальной вероятностью принять <tex>x</tex>. Если <tex>x \in L </tex>, то это происходит с вероятностью 1, иначе с вероятностью не более <tex> \frac{1}{2} </tex>.
 ==Свойства==

← Предыдущая		Версия 08:53, 3 июня 2010
Строка 38:		Строка 38:

	Если же графы изоморфны, то полученное <tex>j</tex> может быть равновероятно равно <tex>1</tex> или <tex>2</tex>, потому вероятность "обмана" <tex>V</tex> равна <tex>\frac{1}{2}</tex>.		Если же графы изоморфны, то полученное <tex>j</tex> может быть равновероятно равно <tex>1</tex> или <tex>2</tex>, потому вероятность "обмана" <tex>V</tex> равна <tex>\frac{1}{2}</tex>.
		+
		+	==Дополнительные материалы==
		+	*[http://en.wikipedia.org/wiki/Probabilistically_checkable_proof] Wikipedia - The Free Encyclopedia

@@ Строка 20: / Строка 20: @@
 # '''PCP[log(n), O(1)] = [[NP|NP]]''' ([[PCP-теорема]])
-==Теорема==
+==Пример==
 '''[[GNI]]''' ∈ '''PCP[poly(n), O(1)]'''

@@ Строка 24: / Строка 24: @@
 ==Доказательство==
-Алгоритм работы машины '''V''' аналогичен алгоритму работы при доказательстве того, что '''[[GNI]]''' ∈ '''IP'''.
+Алгоритм работы машины <tex>V</tex> аналогичен алгоритму работы при доказательстве того, что '''[[GNI]]''' ∈ '''IP'''.
 В строке <tex>\pi</tex> для каждого графа (введена некоторая нумерация графов) записано, кому из данных графов <tex>G_1, G_2</tex> он изоморфен.

@@ Строка 2: / Строка 2: @@
 Классом '''PCP[r(n), q(n)]''' ('''PCP''' - Probabilistically Checkable Proof), где <tex>n</tex> - длина входного слова, называется множество языков, распознаваемых машиной <tex>V^{\pi}(x)</tex>, обладающей следующими свойствами:
-) Время работы <tex>V^{\pi}(x)</tex> ограничено сверху некоторым полиномом от длины <tex>x</tex>
+# Время работы <tex>V^{\pi}(x)</tex> ограничено сверху некоторым полиномом от длины <tex>x</tex>.
+# <tex>\pi</tex> - некоторая строка, выступающая в качестве средства доказательства (аналогично P в [[Класс IP|интерактивном протоколе доказательства]]). Очевидно, ее длина не превосходит 2<sup>poly(x)</sup>, так как только к такому множеству позиций сможет обратиться <tex>V</tex>.
-) <tex>\pi</tex> - некоторая строка, выступающая в качестве средства доказательства (аналогично P в [[Класс IP|интерактивном протоколе доказательства]]). Очевидно, ее длина не превосходит 2<sup>poly(x)</sup>, так как только к такому множеству позиций сможет обратиться <tex>V</tex>
+# <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]], обращающаяся к случайной ленте не более <tex>r(n)</tex> раз.
+# <tex>V</tex> обращается к строке <tex>\pi</tex> не более <tex>q(n)</tex> раз.
-) <tex>V</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]], обращающаяся к случайной ленте не более <tex>r(n)</tex> раз
+# <tex>x \in L \Rightarrow \exists \pi : Pr(V^{\pi}(x)=1)=1 \ </tex> , где <tex>Pr(V^{\pi}(x)=1)</tex> - вероятность того, что <tex>V</tex> допустит <tex>x</tex>.
+# <tex>\  x \notin L \Rightarrow \forall \pi : Pr(V^{\pi}(x)=1)\le \frac{1}{2} </tex>.
 ==Свойства==
-) '''PCP[0, 0] = [[P|P]]''' (по определению '''P''' - нет случайности и обращений к <tex>\pi</tex>)
+# '''PCP[0, 0] = [[P|P]]''' (по определению '''P''' - нет случайности и обращений к <tex>\pi</tex>)
-) '''PCP[log(n), 0] = [[P|P]]''' (логарифмическое число обращений к случайной ленте не помогают, так как можно за полиномиальное время перебрать всевозможные результаты обращений)
+==Теорема==
-) '''PCP[0, log(n)] = [[P|P]]''' (логарифмическое число обращений к строке <tex>\pi</tex> также не помогают, так как можно аналогичным образом перебрать всевозможные результаты обращений за полиномиальное время)
+'''[[GNI]]''' ∈ '''PCP[poly(n), O(1)]'''
-) '''PCP[poly(n), 0] = [[Сложностные_классы_RP_и_coRP|coRP]]''' (по определению '''coRP''')
+==Доказательство==
-) '''PCP[0, poly(n)] = [[NP|NP]]''' (по определению '''NP''' на языке сертификатов)
+Алгоритм работы машины '''V''' аналогичен алгоритму работы при доказательстве того, что '''[[GNI]]''' ∈ '''IP'''.
-) '''PCP[log(n), O(1)] = [[NP|NP]]''' ([[PCP-теорема]])
+В строке <tex>\pi</tex> для каждого графа (введена некоторая нумерация графов) записано, кому из данных графов <tex>G_1, G_2</tex> он изоморфен.