Classes of pebble games and complete problems

Abstract

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.