Pebbling with an auxiliary pushdown

AbstractA pebble game on graphs is introduced which bears the same relationship to the ordinary pebble game as auxiliary pushdown machines bear to ordinary machines. The worst-case time-space trade-off for pebbling with an auxiliary pushdown is shown to be T = N exp e(NS) (where T denotes time, S denotes space and N denotes the size of the graph), which contrasts with T = N exp exp e(NS) for ordinary pebbling. The significance of this result to various questions concerning relations among complexity classes is discussed