Список заданий по ТВС весна 2016

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

<wikitex>

1. (12) TPQBF - множество истиных булевых формул с кванторами в предваренной форме. Говорят, то формула находится в предваренной форме, если она имеет вид $Qx_1Qx_2...Qx_n\varphi(x_1, x_2, \ldots, x_n)$, где $Q$ - кванторы, а $\varphi$ - булева формула. Докажите, что TPQBF является PS-полным.
2. (13) TPQBCNF - множество истиных булевых формул с кванторами в предваренной форме и КНФ. Такие формулы имеют вид вид $Qx_1Qx_2...Qx_n\varphi(x_1, x_2, \ldots, x_n)$, где $Q$ - кванторы, а $\varphi$ - булева формула в КНФ. Докажите, что TPQBCNF является PS-полным.
3. (22) Игра Generalized Geography происходит по следующим правилам. Задан ориентированный граф $G$% и стартовая вериша в нем, в которой исходно находится фишка. Два игрока делают ходы по очереди. Очередным ходом игрок выбирает исходящее из текущей вершины ребро и перемещает фишку по нему. При этом запрещается повторно посещать уже посещенные вершины. Игрок, который не может сделать ход, проигрывает. Язык GG - множество пар "граф-начальная вершина", где в соответствующей игре выигрывает первый игрок. Докажите, что язык GG является PS-полным. Указание: сведите к нему язык TPQBCNF
4. (27) Вершинная игра Шеннона на графе происходит по следующим правилам. Задан неориентированный граф $G$% и вершины $s$ и $t$ в нем, два игрока: Link и Cut делают ходы по очереди. Очередным своим ходом игрок Link выбирает вершину и помечает ее как неуязвимую, а игрок Cut выбирает вершину, не помеченную ранее игроком Link, и удаляет ее. Удалять вершины $s$ и $t$ запрещается. Link выигрывает, если в графе существует путь по неуязвимым вершинам от $s$ до $t$. Язык VSG - множество троек "граф-$s$-$t$", где в соответствующей игре выигрывает Link. Докажите, что язык VSG является PS-полным. Указание: сведите к нему язык TPQBCNF

</wikitex>