Classes of Pebble Games and Complete Problems
Takumi Kasai, Akeo Adachi, Shigeki Iwata · SIAM Journal on Computing · 1979
A “pebble game” is introduced and some restricted pebble games are considered. It is shown that in each of these games the problem to determine whether there is a winning strategy (two-person game) is harder than the solvability problem (one-person game). We also show that each of these problems is complete in well-known complexity classes. Several familiar games are presented whose winning strategy problems are complete in exponential time.