跳到主要内容

广义地理问题

给定一个有向图 GG 和起始点 bb,定义游戏规则为两人从起始点开始交替延长路径,这些路径之间的节点不能重复。

定义问题 GG 为在 G,b\langle G,b\rangle 上第一个玩家具有常胜策略。

广义地理问题是 PSPACE 完全复杂度类的。