CMU-CS-85-101
Computer Science Department
School of Computer Science, Carnegie Mellon University

CMU-CS-85-101

White Pebbles Help

Robert Wilber

December 1984

A family of directed acyclic graphs of vertex indegree 2 is constructed for which there are strategies of the black-white pebble game that use asymptotically fewer pebbles than the best strategies of the black pebble game. This shows that there are straight-line programs that can be evaluated nondeterministically with asymptotically less space than is required by any deterministic evaluation.

14 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]