The two-player pebble game of Dymond–Tompa is identified as a barrier for existing techniques to save space or to speed up parallel algorithms for evaluation problems.

Many combinatorial lower bounds to study L versus NL and NC versus P under different restricted settings scale in the same way as the pebbling algorithm of Dymond–Tompa. These lower bounds include,

• the monotone separation of m-L from m-NL by studying the size of monotone switching networks in Potechin ’10;

• a new semantic separation of NC from P and of NCi from NCi+1 by studying circuit depth, based on the techniques developed for the semantic separation of NC1 from NC2 by the universal composition relation in Edmonds–Impagliazzo–Rudich–Sgall ’01 and in Håstad–Wigderson ’97; and

• the monotone separation of m-NC from m-P and of m-NCi from m-NCi+1 by studying– the depth of monotone circuits in Raz–McKenzie ’99; and– the size of monotone switching networks in Chan–Potechin ’12.

This supports the attempt to separate NC from P by focusing on depth complexity, and suggests the study of combinatorial invariants shaped by pebbling for proving lower bounds. An application to proof complexity gives tight bounds for the size and the depth of some refinements of resolution refutations.