IEICE TRANSACTIONS on Information
Some Two-Person Game is Complete for ACk Under Many-One NC1 Reducibility
Summary :
ACk is the class of problems solvable by an alternating Turing machine in space O(log n) and alternation depth O(logk 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 palyer 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 logk n moves is complete for ACk nuder NC1 reducibility.
- Publication
- IEICE TRANSACTIONS on Information Vol.E77-D No.9 pp.1022-1026
- Publication Date
- 1994/09/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Automata, Languages and Theory of Computing
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shigeki IWATA, "Some Two-Person Game is Complete for ACk Under Many-One NC1 Reducibility" in IEICE TRANSACTIONS on Information,
vol. E77-D, no. 9, pp. 1022-1026, September 1994, doi: .
Abstract: ACk is the class of problems solvable by an alternating Turing machine in space O(log n) and alternation depth O(logk 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 palyer 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 logk n moves is complete for ACk nuder NC1 reducibility.
URL: https://global.ieice.org/en_transactions/information/10.1587/e77-d_9_1022/_p
Copy
@ARTICLE{e77-d_9_1022,
author={Shigeki IWATA, },
journal={IEICE TRANSACTIONS on Information},
title={Some Two-Person Game is Complete for ACk Under Many-One NC1 Reducibility},
year={1994},
volume={E77-D},
number={9},
pages={1022-1026},
abstract={ACk is the class of problems solvable by an alternating Turing machine in space O(log n) and alternation depth O(logk 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 palyer 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 logk n moves is complete for ACk nuder NC1 reducibility.},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - Some Two-Person Game is Complete for ACk Under Many-One NC1 Reducibility
T2 - IEICE TRANSACTIONS on Information
SP - 1022
EP - 1026
AU - Shigeki IWATA
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 1994
AB - ACk is the class of problems solvable by an alternating Turing machine in space O(log n) and alternation depth O(logk 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 palyer 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 logk n moves is complete for ACk nuder NC1 reducibility.
ER -
English
