Список заданий по теории сложности 2021 - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:30:16Z

rollbackEdits.php mass rollback

80.82.78.13 в 04:36, 1 сентября 2022

2022-09-01T04:36:13Z

77.234.215.133 в 08:55, 20 мая 2021

2021-05-20T08:55:40Z

77.234.215.133 в 08:53, 20 мая 2021

2021-05-20T08:53:53Z

77.234.215.133 в 11:35, 18 мая 2021

2021-05-18T11:35:06Z

188.170.214.41 в 12:03, 8 мая 2021

2021-05-08T12:03:12Z

188.170.214.41 в 11:01, 8 мая 2021

2021-05-08T11:01:09Z

188.170.214.41 в 10:52, 8 мая 2021

2021-05-08T10:52:35Z

77.234.215.133 в 08:47, 29 апреля 2021

2021-04-29T08:47:28Z

77.234.215.133 в 16:01, 27 апреля 2021

2021-04-27T16:01:59Z

← Предыдущая		Версия 16:30, 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 Майкл Наки].
−	\|}
−
	# Докажите, что объединение и пересечение языков из $NP$ является языком из $NP$		# Докажите, что объединение и пересечение языков из $NP$ является языком из $NP$
	# Докажите, что конкатенация и замыкание Клини языков $NP$ является языком из $NP$		# Докажите, что конкатенация и замыкание Клини языков $NP$ является языком из $NP$

← Предыдущая		Версия 04:36, 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 Майкл Наки].
		+	\|}
		+
	# Докажите, что объединение и пересечение языков из $NP$ является языком из $NP$		# Докажите, что объединение и пересечение языков из $NP$ является языком из $NP$
	# Докажите, что конкатенация и замыкание Клини языков $NP$ является языком из $NP$		# Докажите, что конкатенация и замыкание Клини языков $NP$ является языком из $NP$

@@ Строка 115: / Строка 115: @@
 # Рассмотрим следующее (неверное) доказательство, что $NP \subset BPP$. Решим для этого $NP$-полную задачу $CIRCUIT-SAT$. Рассмотрим булеву схему в базисе "$\oplus$", "$\wedge$", "$\mathbb{1}$". Превратим её в арифметическую схему, заменив элемент "$\oplus$" на "$+$", а "$\wedge$" на "$\times$". Теперь проверим её на вычисление тождественного нуля с помощью предыдущей задачи. В чём ошибка в рассуждениях?
 # Вероятностный Prover. Докажите, что возможность использовать (свою, отличную от ленты Verifier) вероятностную ленту для Prover не меняет множество языков из $IP$.
-# Запрет на обман. Докажите, что если установить требование, что для слов из языка вероятность недопуска равна 0, то получившийся класс $IP_0 = NP$.
+# Запрет на обман. Докажите, что если установить требование, что для слов не из языка вероятность допуска равна 0, то получившийся класс $IP_0 = NP$.
 # Интерактивное доказательство для перманента, часть 1. Перманент матрицы - $\mathrm{perm}(A)=\sum_{\sigma}\prod_{i=1}^n a_{i\sigma_i}$ - вычисляется по той же формуле, что и определитель, но суммирование происходит без $(-1)^{\mathrm{sign}(\sigma)}$. Можно показать, что вычисление перманента - трудная задача. Докажите формулу разложения перманента по первой строке $\mathrm{perm}(A)=\sum_{i=1}^n a_{1i}\mathrm{perm}(A_{1i})$.
 # Часть 2. Рассмотрим $A_{1i}[j][k]$ как функцию от $i$. Докажите, что для всех $j$ и $k$ она является полиномом от $i$. Какой степени?

@@ Строка 115: / Строка 115: @@
 # Рассмотрим следующее (неверное) доказательство, что $NP \subset BPP$. Решим для этого $NP$-полную задачу $CIRCUIT-SAT$. Рассмотрим булеву схему в базисе "$\oplus$", "$\wedge$", "$\mathbb{1}$". Превратим её в арифметическую схему, заменив элемент "$\oplus$" на "$+$", а "$\wedge$" на "$\times$". Теперь проверим её на вычисление тождественного нуля с помощью предыдущей задачи. В чём ошибка в рассуждениях?
 # Вероятностный Prover. Докажите, что возможность использовать (свою, отличную от ленты Verifier) вероятностную ленту для Prover не меняет множество языков из $IP$.
-# Запрет на обман. Докажите, что если установить требование, что для слов из языка вероятность допуска равна 0, то получившийся класс $IP_0 = NP$.
+# Запрет на обман. Докажите, что если установить требование, что для слов из языка вероятность недопуска равна 0, то получившийся класс $IP_0 = NP$.
 # Интерактивное доказательство для перманента, часть 1. Перманент матрицы - $\mathrm{perm}(A)=\sum_{\sigma}\prod_{i=1}^n a_{i\sigma_i}$ - вычисляется по той же формуле, что и определитель, но суммирование происходит без $(-1)^{\mathrm{sign}(\sigma)}$. Можно показать, что вычисление перманента - трудная задача. Докажите формулу разложения перманента по первой строке $\mathrm{perm}(A)=\sum_{i=1}^n a_{1i}\mathrm{perm}(A_{1i})$.
 # Часть 2. Рассмотрим $A_{1i}[j][k]$ как функцию от $i$. Докажите, что для всех $j$ и $k$ она является полиномом от $i$. Какой степени?

← Предыдущая		Версия 11:35, 18 мая 2021
Строка 111:		Строка 111:
	# Определим класс $BPL$ как класс языков $L$, для которых найдется вероятностная программа $M$, использующая $O(\log n)$ дополнительной памяти, такая что если $P(M(x) = [x \in L]) \ge 2/3$. Докажите, что $BPL \subset P$.		# Определим класс $BPL$ как класс языков $L$, для которых найдется вероятностная программа $M$, использующая $O(\log n)$ дополнительной памяти, такая что если $P(M(x) = [x \in L]) \ge 2/3$. Докажите, что $BPL \subset P$.
	# Докажите, что $BPL \subset SC$.		# Докажите, что $BPL \subset SC$.
		+	# Загадано неотрицательное целое число $a \le 2^{2^n}$. Оракул умеет отвечать на вопрос $q(k) = a \bmod k$. Разработайте вероятностный алгоритм проверки, что $a = 0$, полиномиальный относительно $n$.
		+	# Арифметическая схема - аналог булевой схемы, но на вход она получает $m$-битные неотрицательные целые числа, а вместо функциональных элементов используются арифметические: "$+$", "$-$" и "$\times$". Также на некоторые входы разрешается подать константы. Все вычисления происходят в целых числах. Разработайте вероятностный алгоритм проверки, что заданная арифметическая схема с $n$ арифметическими элементами равна нулю на любых входах, полиномиальный относительно $n$ и $m$.
		+	# Рассмотрим следующее (неверное) доказательство, что $NP \subset BPP$. Решим для этого $NP$-полную задачу $CIRCUIT-SAT$. Рассмотрим булеву схему в базисе "$\oplus$", "$\wedge$", "$\mathbb{1}$". Превратим её в арифметическую схему, заменив элемент "$\oplus$" на "$+$", а "$\wedge$" на "$\times$". Теперь проверим её на вычисление тождественного нуля с помощью предыдущей задачи. В чём ошибка в рассуждениях?
		+	# Вероятностный Prover. Докажите, что возможность использовать (свою, отличную от ленты Verifier) вероятностную ленту для Prover не меняет множество языков из $IP$.
		+	# Запрет на обман. Докажите, что если установить требование, что для слов из языка вероятность допуска равна 0, то получившийся класс $IP_0 = NP$.
		+	# Интерактивное доказательство для перманента, часть 1. Перманент матрицы - $\mathrm{perm}(A)=\sum_{\sigma}\prod_{i=1}^n a_{i\sigma_i}$ - вычисляется по той же формуле, что и определитель, но суммирование происходит без $(-1)^{\mathrm{sign}(\sigma)}$. Можно показать, что вычисление перманента - трудная задача. Докажите формулу разложения перманента по первой строке $\mathrm{perm}(A)=\sum_{i=1}^n a_{1i}\mathrm{perm}(A_{1i})$.
		+	# Часть 2. Рассмотрим $A_{1i}[j][k]$ как функцию от $i$. Докажите, что для всех $j$ и $k$ она является полиномом от $i$. Какой степени?
		+	# Часть 3. Рассмотрим матрицу полиномов $D_A(x)$, элемент которой $D_A(x)[j][k]$ для всех $i$ равен $A_{1i}[j][k]$. Рассмотрим $\mathrm{perm}(D_A(x))$. Докажите, что он является полиномом от $x$. Какой степени?
		+	# Часть 4. На основании предыдущих трех заданий и конструкции интерактивного доказательства для $\#SAT$ разработайте интерактивное доказательство для языка $\langle A, k\rangle$, где $\mathrm{perm}A = k$.
		+	# Назовём язык $L$ самосводимым, если $L \in P^{L^{<n}}$, (обозначение $L^{<n}$ означает, что все вопросы к оракулу имеют длину строго меньше $n$, где $n$ - длина входа). Докажите, что $SAT$ является самосводимым.
		+	# Докажите, что если $L$ самосводим, то $L \in PSPACE$.
		+	# Докажите, что язык $GI$ пар изоморфных графов является самосводимым.
		+	# Докажите, что для языка $GI$ пар изоморфных графов можно, используя самосводимость, за полиномиальное время восстановить перестановку изоморфизма.
		+	# Докажите, что любой язык из $NPC$ является самосводимым.
		+	# Следует ли из доказательства предыдущего задания, что для любого языка $L \in NPC$ и функции проверки сертификатов $R(x, y)$ при условии доступа к оракулу для $L^{<n}$ можно по $x$ за полиномиальное время построить сертификат $y$?

@@ Строка 107: / Строка 107: @@
 # Класс $BP\cdot NP$ определяется как множество $\{A | A \le_r 3SAT\}$. Докажите, что $NP \subset BP\cdot NP$.
 # Докажите, что $BPP \subset BP\cdot NP$.
 # Докажите, что если $\overline{3SAT} \subset BP\cdot NP$, то $PH = \Sigma_3$.
 # Определим класс $BPL$ как класс языков $L$, для которых найдется вероятностная программа $M$, использующая $O(\log n)$ дополнительной памяти, такая что если $P(M(x) = [x \in L]) \ge 2/3$. Докажите, что $BPL \subset P$.

@@ Строка 102: / Строка 102: @@
 # При симуляции $random(n)$ с помощью бросков честной монеты (или абстракции вероятностной ленты) математическое ожидание времени работы $random(n)$ равно $O(\log n)$, но нет ограничения сверху на число бросков. Кажется, что это может испортить определение классов $RP$ или $BPP$, потому что в них время работы программы должно быть ограничено сверху. Докажите, что это не так и можно разрешить конструкции $random(n)$ в вероятностных программах из определения $RP$ или $BPP$, даже если на самом деле в модели вычислений есть доступ к источнику случайности только с распределением честной монеты.
 # Нечестные монеты с нерациональным $p$ могут привести к парадоксам. Докажите, что существует такое $p$, такой неразрешимый язык $L$ и такая программа $A$, что если у программы $A$ есть доступ к источнику случайности с распределением нечестной монеты с вероятностью выпадения $1$ равной $p$, то она может распознать язык $L$ за полиномиальное время.
 # Вероятностные сведения. Будем говорить, что $B$ вероятностно сводится к $C$ и писать $B \le_r C$, если найдется такая вероятностная программа $p$, работающая за полином, что $P([x \in B] = [p(x) \in C]) \ge 2/3$. Докажите, что если $C \in BPP$, $B \le_r C$, то $B \in BPP$.
 # Докажите, что $\le_r$ не является транзитивным отношением.
 # Класс $BP\cdot NP$ определяется как множество $\{A | A \le_r 3SAT\}$. Докажите, что $NP \subset BP\cdot NP$.
 # Докажите, что $BPP \subset BP\cdot NP$.
 # Докажите, что если $\overline{3SAT} \subset BP\cdot NP$, то $PH = \Sigma_3$.

← Предыдущая		Версия 10:52, 8 мая 2021
Строка 100:		Строка 100:
	# Докажите, что если $NP \subset BPP$, то $NP = RP$.		# Докажите, что если $NP \subset BPP$, то $NP = RP$.
	# В определении $ZPP$ нет требования, чтобы на любой вероятностной ленте программа завершалась. Докажите, что если добавить это ограничение, определение класса $ZPP$ не поменяется.		# В определении $ZPP$ нет требования, чтобы на любой вероятностной ленте программа завершалась. Докажите, что если добавить это ограничение, определение класса $ZPP$ не поменяется.
		+	# При симуляции $random(n)$ с помощью бросков честной монеты (или абстракции вероятностной ленты) математическое ожидание времени работы $random(n)$ равно $O(\log n)$, но нет ограничения сверху на число бросков. Кажется, что это может испортить определение классов $RP$ или $BPP$, потому что в них время работы программы должно быть ограничено сверху. Докажите, что это не так и можно разрешить конструкции $random(n)$ в вероятностных программах из определения $RP$ или $BPP$, даже если на самом деле в модели вычислений есть доступ к источнику случайности только с распределением честной монеты.
		+	# Нечестные монеты с нерациональным $p$ могут привести к парадоксам. Докажите, что существует такое $p$, такой неразрешимый язык $L$ и такая программа $A$, что если у программы $A$ есть доступ к источнику случайности с распределением нечестной монеты с вероятностью выпадения $1$ равной $p$, то она может распознать язык $L$ за полиномиальное время.
		+	# Вероятностные сведения. Будем говорить, что $B$ вероятностно сводится к $C$ и писать $B \le_r C$, если найдется такая вероятностная программа $p$, работающая за полином, что $P([x \in B] = [p(x) \in C]) \ge 2/3$. Докажите, что если $C \in BPP$, $B \le_r C$, то $B \in BPP$.
		+	# Докажите, что $\le_r$ не является транзитивным отношением.
		+	# Класс $BP\cdot NP$ определяется как множество $\{A \| A \le_r 3SAT\}$. Докажите, что $NP \subset BP\cdot NP$.
		+	# Докажите, что $BPP \subset BP\cdot NP$.
		+	# Определим язык $UNIQUE-SAT$ как множество удовлетворимых булевых формул, которые имеют единственное удовлетворяющее назначение. Докажите, что $UNIQUE-SAT \in BP\cdot NP$.
		+	# Докажите, что если $\overline{3SAT} \subset BP\cdot NP$, то $PH = \Sigma_3$.

@@ Строка 88: / Строка 88: @@
 # Докажите, что $NC^1 \subset L$ ($L$ здесь log space).
 # Альтернативное определение $ZPP$. Докажите, что $L \in ZPP$ тогда и только тогда, когда существует вероятностная программа $p$, которая работает за полиномиальное время, выдает 0 1 или 2, если она выдает 0 или 1, то это значение равно $x \in L$, а 2 ("не знаю") возвращается с вероятностью не больше 1/2.
-# Докажите, что $ZPP = RP \cup coRP$.
+# Докажите, что $ZPP = RP \cap coRP$.
 # Докажите, что $BPP \subset PS$.
 # Докажите, что $RP \subset NP$.
@@ Строка 95: / Строка 95: @@
 # Докажите, что если для $L$ найдется программа $M$ с полиномиальным временем работы и полином $p > 0$, такие что $P(M(x) = [x \in L]) \ge \frac{1}{2} + \frac{1}{p(|x|)}$, то $L \in BPP$.
 # Докажите, что если $L \in BPP$, то для любого полинома $p > 1$ найдется программа $M$ с полиномиальным временем работы, такая что $P(M(x) = [x \in L]) \ge 1 - 2^{-p(|x|)}.$
-# Определим класс $RL$ как класс языков $L$, для которых найдется вероятностная программа $M$, использующая $O(\log |w|)$ дополнительной памяти, такая что если $x \in L$, то $P(M(x) = 1) \ge 1/2$, если $x \notin L$, то $P(M(x) = 1) = 0$. Докажите, что $RL \subset P$
+# Определим класс $RL$ как класс языков $L$, для которых найдется вероятностная программа $M$, использующая $O(\log n)$ дополнительной памяти, такая что если $x \in L$, то $P(M(x) = 1) \ge 1/2$, если $x \notin L$, то $P(M(x) = 1) = 0$. Докажите, что $RL \subset P$
 # Докажите, что задача проверки того, что в неориентированном графе есть путь из $s$ в $t$, лежит в $RL$.
 # Почему решение предыдущей задачи не удается распространить на ориентированные графы?
 # Докажите, что если $NP \subset BPP$, то $NP = RP$.
 # В определении $ZPP$ нет требования, чтобы на любой вероятностной ленте программа завершалась. Докажите, что если добавить это ограничение, определение класса $ZPP$ не поменяется.

← Предыдущая		Версия 16:01, 27 апреля 2021
Строка 87:		Строка 87:
	# Выведите из предыдущего задания, что $NL \subset NC$.		# Выведите из предыдущего задания, что $NL \subset NC$.
	# Докажите, что $NC^1 \subset L$ ($L$ здесь log space).		# Докажите, что $NC^1 \subset L$ ($L$ здесь log space).
		+	# Альтернативное определение $ZPP$. Докажите, что $L \in ZPP$ тогда и только тогда, когда существует вероятностная программа $p$, которая работает за полиномиальное время, выдает 0 1 или 2, если она выдает 0 или 1, то это значение равно $x \in L$, а 2 ("не знаю") возвращается с вероятностью не больше 1/2.
		+	# Докажите, что $ZPP = RP \cup coRP$.
		+	# Докажите, что $BPP \subset PS$.
		+	# Докажите, что $RP \subset NP$.
		+	# Обозначим как $PP^+$ как класс языков, для которых существует вероятностная программа $M$, работающая за полином, что если $x \in L$, то $P(M(x) = 1) > 1/2$, а если $x \notin L$, то $P(M(x) = 0) \ge 1/2$. Докажите, что $PP^+ = PP$.
		+	# Докажите, что $NP \subset PP$.
		+	# Докажите, что если для $L$ найдется программа $M$ с полиномиальным временем работы и полином $p > 0$, такие что $P(M(x) = [x \in L]) \ge \frac{1}{2} + \frac{1}{p(\|x\|)}$, то $L \in BPP$.
		+	# Докажите, что если $L \in BPP$, то для любого полинома $p > 1$ найдется программа $M$ с полиномиальным временем работы, такая что $P(M(x) = [x \in L]) \ge 1 - 2^{-p(\|x\|)}.$
		+	# Определим класс $RL$ как класс языков $L$, для которых найдется вероятностная программа $M$, использующая $O(\log \|w\|)$ дополнительной памяти, такая что если $x \in L$, то $P(M(x) = 1) \ge 1/2$, если $x \notin L$, то $P(M(x) = 1) = 0$. Докажите, что $RL \subset P$
		+	# Докажите, что задача проверки того, что в неориентированном графе есть путь из $s$ в $t$, лежит в $RL$.
		+	# Почему решение предыдущей задачи не удается распространить на ориентированные графы?
		+	# Докажите, что если $NP \subset BPP$, то $NP = RP$.
		+	# В определении $ZPP$ нет требования, чтобы на любой вероятностной ленте программа завершалась. Докажите, что если добавить это ограничение, определение класса $ZPP$ не поменяется.