On the power of white pebbles (Q1180416)

Pebble games are played on directed acyclic graphs by placing and removing pebbles according to certain rules. The Black pebble game was introduced by Hewitt and Paterson to model the deterministic evaluation of straight-line programs where the pebbles correspond to the space used in the evaluation process. Cook and Sethi introduced the Black-White pebble game to model the nondeterministic evaluation of straight-line programs. The white pebbles are intended to model the nondeterministic choice. The rules of the Black pebble game are: (1) A black pebble may be placed on a vertex \(v\) if and only if all immediate predecessors of \(v\) have pebbles. (2) A black pebble can be removed from a vertex at any time. For the Black-White pebble game two extra rules are added: (3) A white pebble can be placed on a vertex at any time. (4) A white pebble can be removed from node \(v\) if and only if all immediage predecessors of \(v\) have pebbles. Starting with a pebble-free graph the goal is to pebble all the vertices while attempting to use as few pebbles as possible. A strategy is a sequence of moves that achieves this goal. By comparing the two games we learn about the trade-offs between nondeterminism and space resources. The authors construct a family of directed acyclic graphs \((G_ p | p)\) such that any Black pebble game strategy for \(G_ p\) requires \(p^ 2\) pebbles, whereas \(3p+1\) pebbles suffice when white pebbles are allowed.