Some Two-Person Game is Complete for AC^k Under Many-One NC^1 Reducibility

スポンサーリンク

概要

• 論文の詳細を見る

• AC^k is the class of problems solvable by an alternating Turing machine in space O(log n) and alternation depth O(log^k n)[S.A.Cook, A taxonomy of problems with fast parallel algorithms, Inform. Contr. vol.64]. We consider a game played by two persons: each player alternately moves a marker along an edge of a given digraph, and the first player who cannot move loses the game. It is shown that the problem to determine whether the first player can win the game on a digraph with n nodes exactly after log^k n moves is complete for AC^k under NC^1 reducibility.

• 社団法人電子情報通信学会の論文
• 1994-09-25

著者

• Iwata Shigeki

  Faculty of Electro-Communications, University of Electro-Communications

• Iwata Shigeki

  Faculty Of Electro-communications University Of Electro-communications

関連論文

• Exhaustive Computation to Derive the Lower Bound for Sorting 13 Items
• Some Two-Person Game is Complete for AC^k Under Many-One NC^1 Reducibility

スポンサーリンク