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