The complexity of short two-person games. (English) Zbl 0742.90089
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. A. Chandra, D. Kozen and 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 E. Berlekamp, J. Conway and 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.
The authors define a specific two-person game of perfect information called Shortcake after a fashion of a game termed Cutcake of E. Berlekamp, J. Conway and 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.
Reviewer: A.Lewis (Irvine)
MSC:
| 91A05 | 2-person games |
| 03D10 | Turing machines and related notions |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | Berlekamp, E. R.; Conway, J. H.; Guy, R. K., Games in general, (Winning Ways for your Mathematical Plays, Vol. 1 (1982), Academic Press: Academic Press London) · Zbl 0485.00025 |
| [2] | Berlekamp, E. R.; Conway, J. H.; Guy, R. K., Games in particular, (Winning Ways for your Mathematical Plays, Vol. 2 (1982), Academic Press: Academic Press London) · Zbl 0485.00025 |
| [3] | Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, J. ACM, 28, 1, 114-133 (1981) · Zbl 0473.68043 |
| [4] | Cook, S. A., A taxonomy of problems with fast parallel algorithms, Inform. and Control, 64, 1-3, 2-22 (1985) · Zbl 0575.68045 |
| [5] | Dymond, P. W.; Tompa, M., Speedups of deterministic machines by synchronous parallel machines, J. Comput. System Sci., 30, 2, 149-161 (1985) · Zbl 0589.68040 |
| [6] | Garey, M. R.; Johnson, D. S., Computers and Intractability: a Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039 |
| [7] | Goldschlager, L. M., The monotone and planar circuit value problems are log space complete for P, SIGACT New, 9, 2, 25-29 (1977) · Zbl 0356.94042 |
| [8] | Ruzzo, W. L., Tree-size bounded alternation, J. Comput. System Sci., 21, 2, 218-235 (1980) · Zbl 0445.68034 |
| [9] | Ruzzo, W. L., On uniform circuit complexity, J. Comput. System Sci., 22, 3, 365-383 (1981) · Zbl 0462.68013 |
| [10] | Schaefer, T. J., On the complexity of some two-person perfect-information games, J. Comput. System Sci., 16, 185-225 (1978) · Zbl 0383.90112 |
| [11] | Spencer, J., Ten Lectures on the Probabilistic Method, (CBMS-NSF Regional Conference Series in Applied Mathematics, 52 (1987), SIAM: SIAM Philadelphia, PA) · Zbl 0703.05046 |
| [12] | Stockmeyer, L.; Vishkin, U., Simulation of parallel random access machines by circuits, SIAM J. Comput., 13, 2, 409-422 (1984) · Zbl 0533.68048 |
| [13] | Sudborough, I. H., On the tape complexity of deterministic context-free languages, J. ACM, 25, 3, 405-414 (1978) · Zbl 0379.68054 |
| [14] | Ullman, J. D., Computational Aspects of VLSI (1984), Computer Science Press: Computer Science Press Rockville, MD · Zbl 0539.68021 |
| [15] | Venkateswaran, H., Properties that characterize LOGCFL, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 141-150 (1987) · Zbl 0776.68046 |
| [16] | Venkateswaran, H.; Tompa, M., A new pebble game that characterizes parallel complexity classes, SIAM J. Comput., 18, 3, 533-549 (1989) · Zbl 0678.68047 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
