Pebble Games, Proof Complexity, and Time-Space Trade-offs

摘要

Pebble games were extensively studied in the 1970s and 1980s in a number ofdifferent contexts. The last decade has seen a revival of interest in pebblegames coming from the field of proof complexity. Pebbling has proven to be auseful tool for studying resolution-based proof systems when comparing thestrength of different subsystems, showing bounds on proof space, andestablishing size-space trade-offs. This is a survey of research in proofcomplexity drawing on results and tools from pebbling, with a focus on proofspace lower bounds and trade-offs between proof size and proof space.