Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
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
Nimrod Megiddo
Journal of Symbolic Computation
Hans Becker, Frank Schmidt, et al.
Photomask and Next-Generation Lithography Mask Technology 2004
Michael Ray, Yves C. Martin
Proceedings of SPIE - The International Society for Optical Engineering