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

Список заданий по теории сложности 2022

2022-03-07T10:44:34Z

165.231.178.60:

# Докажите, что объединение, пересечение, конкатенация и замыкание Клини языков из $NP$ является языком из $NP$
# В определении $NP$ мы говорим, что при любом недетерминированном выборе программа должна завершиться не более чем за $p(n)$, где $p$ - полином, а $n$ - длина входа. На самом деле это требование может быть ослаблено, можно требовать, чтобы программа завершалась не более чем за $p(n)$ только в случае допуска. Докажите, что в таком определении класс $NP$ не меняется.
# $PRIMES\in NP$. Язык $PRIMES$ определяется следующим образом: это множество двоичных записей простых целых чисел. Доказательство принадлежности $PRIMES$ классу $NP$ разбито на два задания. Часть 1. Известно, что если $n$ простое, то существует $g$, такое что $g^{n-1}=1\pmod n$ и для всех $1 \le k < n - 1$ выполнено $g^k \ne 1 \pmod n$. Пусть известно разложение $n-1$ на простые множители: $n-1=q_1^{a_1}q_2^{a_2}\ldots q_k^{a_k}$. Предложите полиномиальный алгоритм проверки, что заданное $g$ удовлетворяет описанному условию. Можно недетерминированно выбрать $g$ и недетерминированно угадать разбиение $n-1$ на простые множители. Однако это требует проверки на простоту, чтобы убедиться, что угадано разложение именно на простые множители. Завершите доказательство, что $PRIMES \in NP$, описав рекурсивную процедуру проверки и доказав, что она работает за полиномиальное время.
# Задача останова $HALT = \{\langle m, x \rangle | m$ - детерминированная машина Тьюринга, $m(x) = 1\}$. Докажите, что $HALT$ является $NP$-трудной. Является ли она $NP$-полной?
# Изоморфизм подграфа $NP$-полный. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G_1, G_2 \rangle | G_1$ содержит $G_2$ как подграф $\}$.
# Задача о покрытии подмножествами $NP$-полна. Докажите $NP$-полноту следующего языка. Даны $n$ множеств $S_i\subset\{1, 2, \ldots, m\}$ и число $k$. Язык наборов $SETCOVER = \{ \langle [S_1, S_2, \ldots, S_n], k\rangle$ можно выбрать не более $k$ множеств, чтобы каждый элемент от $1$ до $m$ лежал хотя бы в одном выбранном множестве $\}$.
# Задача поиска доминирующего множества $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $DOM = \{\langle G, k \rangle | G$ содержит множество из $k$ вершин, таких, что любая вершина $G$ либо выбрана, либо имеет выбранного соседа $\}$.
# Задача о раскраске в три цвета $NP$-полна. Докажите $NP$-полноту следующего языка. Множество графов $3COL=\{ G | G$ имеет правильную раскраску в три цвета $\}$. Что можно сказать про раскраску в два цвета?
# Задача о рюкзаке $NP$-полна. Докажите $NP$-полноту следующего языка. Даны предметы с весом $w_i$ и стоимостью $v_i$. Язык наборов $KNAPSACK=\{ \langle s, [(v_1, w_1), (v_2, w_2), \ldots (v_n, w_n)], k\rangle | $ можно выбрать предметы с суммарным весом не более $s$ и суммарной стоимостью не менее $k \}$.
# Задача целочисленного линейного программирования $NP$-трудна. Докажите $NP$-трудность следующего языка. Множество систем линейных ограничений, которые имеют целочисленное решение.
# Неориентированный гамильтонов цикл. Докажите, что язык $UHAM = \{G | G$ - неориентированный граф, содержащий гамильтонов цикл$\}$ является $NP$-полным.
# Ориентированный гамильтонов путь. Докажите, что язык $HAMP = \{G | G$ - ориентированный граф, содержащий гамильтонов путь$\}$ является $NP$-полным.
# Говорят, что булева формула с кванторами находится в предваренной форме, если сначала идут все кванторы, а затем булева формула: $Qx_1Qx_2\ldots Qx_n \varphi(x_1,\ldots, x_n)$, где $Q = \forall$ или $Q = \exists$. Говорят, что булева формула с кванторами находится в КНФ, если она находится в предваренной форме $Qx_1Qx_2\ldots Qx_n \varphi(x_1,\ldots, x_n)$, где $Q = \forall$ или $Q = \exists$, причём $\varphi$ находится в КНФ. Говорят, что булева формула с кванторами находится в 3-КНФ, если она находится в предваренной форме $Qx_1Qx_2\ldots Qx_n \varphi(x_1,\ldots, x_n)$, где $Q = \forall$ или $Q = \exists$, причём $\varphi$ находится в 3-КНФ. Докажите, что язык истиных булевых формул с кванторами в 3-КНФ является $PS$-полным.
# $PS$-полнота Generalized Geography. Игра в Generalized Geography (GG) ведется на поле, которое представляет собой ориентированный граф с выделенной стартовой вершиной. Исходно фишка находится в стартовой вершине. Два игрока делают ходы по очереди, за один ход игрок перемещает фишку по ребру из текущей вершины. Запрещается перемещать фишку в вершину, где она уже ранее была. Игрок, который не может сделать ход, проигрывает. Докажите, что $GG = \{\langle G, s\rangle|$ первый игрок выигрывает на графе $G$ со стартовой вершиной $s\}$ является $PS$-полным языком.
# $PS$-полнота Shannon Switching Game. Игра Шеннона ведется на поле, которое представляет собой неориентированный граф с двумя выделенными вершинами $s$ и $t$. Два игрока Short и Cut делают ходы по очереди, Short ходит первым. За один ход Short может выбрать одну вершину и защитить её. За один ход Cut может удалить любую вершину, кроме $s$, $t$ и защищенных к текущему моменту вершин. В конце Short выигрывает, если по защищенным вершинам можно добраться от $s$ до $t$. Докажите, что $SHSW = \{\langle G, s, t\rangle|$ Short выигрывает на графе $G$ с выделенными вершиными $s$ и $t\}$ является $PS$-полным языком.
# $PS$-трудность языка полных регулярных выражений. Докажите, что $FRE = \{\langle \varphi\rangle|$ любое слово подходит под регулярное выражение $\varphi\}$ является $PS$-трудным языком.

Список заданий по ТИгр 2022 весна

2022-02-15T11:42:44Z

165.231.178.60:

# Для комбинаторной игры $A=\{L|R\}$ определим игру $-A$. $-0=0$, для других игр пусть $L=\{g^L_1, g^L_2, \ldots\}$, $R=\{g^R_1, g^R_2, \ldots\}$, определим $-L=\{-g^L_1, -g^L_2, \ldots\}$, $-R$ определяется аналогично, $-A = \{-R|-L\}$. Что можно сказать про игру $A+(-A)$? Далее будем обозначать игру $A + (-B)$ как $A-B$.
# На лекции было введено определение эквивалентности $A \approx B$ если для любой игры $C$ исход $A+C$ и $B+C$ одинаковый. Можно ввести альтернативное определение: скажем, что $A\approx B$, если $A-B$ проигрышная для текущего игрока (класс $P$). Докажите, что эти определения дают одно и то же отношение эквивалентности. Далее нам не очень интересно различать эквивалентные игры, поэтому мы будем для простоты называть их равными и использовать значок $=$.
# Докажите формально, что сумма игр ассоциативна и коммутативна.
# Профессор дал неправильное определение и определил противоположную игру для $A=\{L|R\}$ как $\mathbin{\scriptstyle\dot{\smash{\textstyle-}}} A = \{R|L\}$. Поясните, почему определение профессора плохо подходит для введения операции "минус" на играх.
# Профессор дал неправильное определение и определил противоположную игру для $A=\{L|R\}$ как $!A = \{!L|!R\}$. Поясните, почему определение профессора плохо подходит для введения операции "минус" на играх.
# Будем говорить, что игра $A$ является положительной, если в ней выигрывает игрок L и писать $A>0$. Докажите, что если $A > 0$ и $B > 0$, то $A+B>0$.
# Будем говорить, что $A > B$, если $A-B>0$. Докажите, что отношение $>$ является антирефлексивным, антисимметричным и транзитивным (строгий порядок).
# Определим неотрицательные целые числа по формуле $G_0 = \{|\}$, $G_n = \{G_{n-1}|\}$ (далее мы будем вместо $G_n$ писать просто $n$, но в этом задании без отдельного обозначения не обойтись). Докажите, что $G_n+G_m = G_{n+m}$.
# Определите отрицательные целые числа. Докажите, что все законы для целых чисел как для группы по сложению выполнены. Мы вернемся к числам в одной из ближайших лекций, а пока переключаемся на матричные игры.
# Приведите пример биматричной игры, в которой есть более одной различной точки равновесия по Нэшу, выигрыши игроков в которых различаются.
# Лемма о масштабе Пусть матрица $A$ имеет седловую точку. Рассмотрим матрицу $B$, определенную соотношением $b_{ij} = ka_{ij}+d$, $k > 0$. Докажите, что матрица $B$ имеет седловую точку, причем множества координат седловых точек этих матриц совпадают.
# Рассмотрим пример экономической игры с бесконечным множеством стратегий: дуополия Курно. На рынке есть две фирмы, стратегии которых заключаются в производстве $q_1$ и $q_2$ товара, соответственно. Цена за единицу товара равна $p-q_1-q_2$. Себестоимость единицы товара $c$. Соответственно, выигрыши игроков равны $u_1(q_1,q_2)=(p-q_1-q_2-c)q_1$ и $u_2(q_1,q_2)=(p-q_1-q_2-c)q_2$. Найдите равновесие по Нэшу для дуополии Курно.
# Дуополия Бертрана. На рынке есть две фирмы, которые производят различные товары $A$ и $B$, соответственно, а их стратегии заключаются в установлении цены на товары $c_1$ и $c_2$, соответственно. После этого фирмы продают $Q_1 = q-c_1+kc_2$ и $Q_2 = q-c_2+kc_1$ единиц товара, соответственно. Себестоимость единицы товара $c$. Запишите выигрыши игроков в дуополии Бертрана и найдите равновесие по Нэшу.

Список заданий по ТИгр 2022 весна

2022-02-15T11:31:23Z

165.231.178.60:

# Для комбинаторной игры $A=\{L|R\}$ определим игру $-A$. $-0=0$, для других игр пусть $L=\{g^L_1, g^L_2, \ldots\}$, $R=\{g^R_1, g^R_2, \ldots\}$, определим $-L=\{-g^L_1, -g^L_2, \ldots\}$, $-R$ определяется аналогично, $-A = \{-R|-L\}$. Что можно сказать про игру $A+(-A)$? Далее будем обозначать игру $A + (-B)$ как $A-B$.
# На лекции было введено определение эквивалентности $A \approx B$ если для любой игры $C$ исход $A+C$ и $B+C$ одинаковый. Можно ввести альтернативное определение: скажем, что $A\approx B$, если $A-B$ проигрышная для текущего игрока (класс $P$). Докажите, что эти определения дают одно и то же отношение эквивалентности. Далее нам не очень интересно различать эквивалентные игры, поэтому мы будем для простоты называть их равными и использовать значок $=$.
# Докажите формально, что сумма игр ассоциативна и коммутативна.
# Профессор дал неправильное определение и определил противоположную игру для $A=\{L|R\}$ как $\mathbin{\scriptstyle\dot{\smash{\textstyle-}}} A = \{R|L\}$. Поясните, почему определение профессора плохо подходит для введения операции "минус" на играх.
# Профессор дал неправильное определение и определил противоположную игру для $A=\{L|R\}$ как $!A = \{!L|!R\}$. Поясните, почему определение профессора плохо подходит для введения операции "минус" на играх.
# Будем говорить, что игра $A$ является положительной, если в ней выигрывает игрок L и писать $A>0$. Докажите, что если $A > 0$ и $B > 0$, то $A+B>0$.
# Будем говорить, что $A > B$, если $A-B>0$. Докажите, что отношение $>$ является антирефлексивным, антисимметричным и транзитивным (строгий порядок).
# Определим неотрицательные целые числа по формуле $G_0 = \{|\}$, $G_n = \{G_{n-1}|\}$ (далее мы будем вместо $G_n$ писать просто $n$, но в этом задании без отдельного обозначения не обойтись). Докажите, что $G_n+G_m = G_{n+m}$.
# Определите отрицательные целые числа. Докажите, что все законы для целых чисел как для группы по сложению выполнены. Мы вернемся к числам в одной из ближайших лекций, а пока переключаемся на матричные игры.
# Приведите пример биматричной игры, в которой есть более одной различной точки равновесия по Нэшу, выигрыши игроков в которых различаются.
# Лемма о масштабе Пусть матрица $A$ имеет седловую точку. Рассмотрим матрицу $B$, определенную соотношением $b_{ij} = ka_{ij}+d$. Докажите, что матрица $B$ имеет седловую точку, причем множества координат седловых точек этих матриц совпадают.
# Рассмотрим пример экономической игры с бесконечным множеством стратегий: дуополия Курно. На рынке есть две фирмы, стратегии которых заключаются в производстве $q_1$ и $q_2$ товара, соответственно. Цена за единицу товара равна $p-q_1-q_2$. Себестоимость единицы товара $c$. Соответственно, выигрыши игроков равны $u_1(q_1,q_2)=(p-q_1-q_2-c)q_1$ и $u_2(q_1,q_2)=(p-q_1-q_2-c)q_2$. Найдите равновесие по Нэшу для дуополии Курно.
# Дуополия Бертрана. На рынке есть две фирмы, которые производят различные товары $A$ и $B$, соответственно, а их стратегии заключаются в установлении цены на товары $c_1$ и $c_2$, соответственно. После этого фирмы продают $Q_1 = q-c_1+kc_2$ и $Q_2 = q-c_2+kc_1$ единиц товара, соответственно. Себестоимость единицы товара $c$. Запишите выигрыши игроков в дуополии Бертрана и найдите равновесие по Нэшу.

Список заданий по теории сложности 2022

2022-02-13T11:23:37Z

165.231.178.60: Новая страница: «# Докажите, что объединение, пересечение, конкатенация и замыкание Клини языков из $NP$ явл…»