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

<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>