A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
Paper
The complexity of short two-person games
Abstract
Cook posed the question of finding a natural problem that is complete for AC1. It is shown here that a certain two-person game of perfect information is such a problem. Variants of this game are shown to be complete for P and for LOGCFL. © 1990.
Related
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.
M. Tismenetsky
International Journal of Computer Mathematics