Generalized Chat Noir is PSPACE-Complete

スポンサーリンク

概要

• 論文の詳細を見る

• We study the computational complexity of the following two-player game. The instance is a graph G=(V,E), an initial vertex s ∈ V, and a target set T ⊆ V. A "cat" is initially placed on s. Player 1 chooses a vertex in the graph and removes it and its incident edges from the graph. Player 2 moves the cat from the current vertex to one of the adjacent vertices. Players 1 and 2 alternate removing a vertex and moving the cat, respectively. The game continues until either the cat reaches a vertex of T or the cat cannot be moved. Player 1 wins if and only if the cat cannot be moved before it reaches a vertex of T. It is shown that deciding whether player 1 has a forced win on the game on G is PSPACE-complete.

著者

• Iwamoto Chuzo

  Graduate School Of Engineering Hiroshima University

• Morita Kenichi

  Graduate School Of Engineering Hiroshima University

• SUMIDA Yuichi

  West Japan Railway Company

• MUKAI Yuta

  Fujitsu Corporation

関連論文

• On the Non-existance of Rotation-Symmetric von Neumann Neighbor Number-Conserving Cellular Automata of Which the State Number is Less than Four
• A Recursive Padding Technique on Nondeterministic Cellular Automata
• Prefix Computations on Iterative Arrays with Sequential Input/Output Mode(Cellular Automata)
• A Logically Universal Number-Conserving Cellular Automaton with a Unary Table-Lookup Function(Cellular Automata)
• Time and Space Complexity Classes of Hyperbolic Cellular Automata(Cellular Automata)
• NP-Hard and k-EXPSPACE-Hard Cast Puzzles
• Generalized Shisen-Sho is NP-Complete
• Generalized Chat Noir is PSPACE-Complete

スポンサーリンク