论文标题
避免游戏是PSPACE完成的
Avoidance games are PSPACE-Complete
论文作者
论文摘要
避免游戏是两名玩家声称超图顶点的游戏，并试图避免一些结构。自1968年引入SIM游戏以来，研究了这些游戏，但其中只有很少的复杂性结果。 2001年，斯拉尼（Slany）证明了Avoider-avoider游戏的复杂性以及2017年Bonnet等人的一些部分结果。事实证明，简短的Avoider-Enforcer游戏是Co-W [1] -hard。最近，在2022年，Miltzow和Stojaković证明了这些游戏是NP-Hard。由于这些游戏对应于1963年推出的著名制造商 - 破坏者游戏的误会版本，并在1978年被证明是Pspace-Complete，因此人们可以期望这些游戏也将是Pspace complete，但此后的问题自那时以来仍然开放。我们在这里证明，Avoider-Averider和Avoider-Enforcer惯例都是PSPACE完成的，因此，某些特定的Avoider-Enforcer游戏也是如此。
Avoidance games are games in which two players claim vertices of a hypergraph and try to avoid some structures. These games are studied since the introduction of the game of SIM in 1968, but only few complexity results are known on them. In 2001, Slany proved some partial results on Avoider-Avoider games complexity, and in 2017 Bonnet et al. proved that short Avoider-Enforcer games are Co-W[1]-hard. More recently, in 2022, Miltzow and Stojaković proved that these games are NP-hard. As these games corresponds to the misère version of the well-known Maker-Breaker games, introduced in 1963 and proven PSPACE-complete in 1978, one could expect these games to be PSPACE-complete too, but the question remained open since then. We prove here that both Avoider-Avoider and Avoider-Enforcer conventions are PSPACE-complete, and as a consequence of it that some particular Avoider-Enforcer games also are.
