Nimrod Megiddo
Journal of Symbolic Computation
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
Moutaz Fakhry, Yuri Granik, et al.
SPIE Photomask Technology + EUV Lithography 2011
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997