17
правок
Изменения
tex tex tex
== Утверждение ==
Язык <tex> GG = \{ <\langle G, b\rangle | </tex> | первый игрок в графе <tex> G</tex>, начиная игру с вершины <tex> b</tex>, обладает выигрышной стратегией <tex> \} </tex> является [[Класс_PS|PS-полным]].
== Доказательство ==
Чтобы показать, что язык принадлежит классу PS, предъявим алгоритм, работающий на полиномиальной памяти, определяющий, обладает ли игрок выигрышной стратегией находясь в вершине v графа G.
Алгоритм <tex> M(<\langle G,vb \rangle ) </tex>):
1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.
