论文标题
Avoider-Enforcer游戏是NP-HARD
Avoider-Enforcer Game is NP-hard
论文作者
论文摘要
在Avoider-enforcer游戏中，我们获得了超图。 Avoider和Enforcer在声称无人认领的顶点替代，直到声称所有超图的顶点为止。如果Avoider声称所有边缘的顶点，执行者将获胜； Avoider获胜。我们表明，决定Avoider是否有胜利策略是NP-HARD。
In an Avoider-Enforcer game, we are given a hypergraph. Avoider and Enforcer alternate in claiming an unclaimed vertex, until all the vertices of the hypergraph are claimed. Enforcer wins if Avoider claims all vertices of an edge; Avoider wins otherwise. We show that it is NP-hard to decide if Avoider has a winning strategy.
