The complexity of short two-person games (Q1173637)

This paper answers an open problem due to Cook; namely, is there a ``natural'' problem which is complete for the class of languages \(AC^ 1\)? If \(k\geq 1\) is an integer, then \(AC^ k\) is the class of languages recognizable by alternating Turing Machines [cf. \textit{A. Chandra, D. Kozen} and \textit{L. Stockmeyer}, ``Alternation'', J. Assoc. Comput. Mach. 28, 114-133 (1981; Zbl 0473.68043)]. It is shown that a source of problems that are complete for \(AC^ 1\) is a class of short (i.e., \(O(\log n)\) moves) two-person games of perfect information. The authors define a specific two-person game of perfect information called Shortcake after a fashion of a game termed Cutcake of \textit{E. Berlekamp, J. Conway} and \textit{R. Guy} [see ``Winning ways for your mathematical plays'' (1982; Zbl 0485.00025)], which is an alternating move game on an \(m\times n\) Boolean matrix between two players: \(H\) and \(V\). If an \(m\times n\) Boolean matrix is generically denoted by \(M\), then informally, Shortcake=\{\(M:H\) has a winning Shortcake strategy on \(M\)\}. For \(NC^ 1\) reduction defined by computations from a uniform family of founded fan-in circuits of \(O(\log n)\) depth, the following is the main theorem of the paper: Theorem. Shortcake is complete for \(AC^ 1\) under many-one \(NC^ 1\) reducibility. Other games and variants for \(P\)- completeness are also formulated and discussed.