Pebble games, proof complexity, and time-space trade-offs
Forskningsoutput: Tidskriftsbidrag › Artikel i vetenskaplig tidskrift
Pebble games were extensively studied in the 1970s and 1980s in a number of different contexts. The last decade has seen a revival of interest in pebble games coming from the field of proof complexity. Pebbling has proven to be a useful tool for studying resolution-based proof systems when comparing the strength of different subsystems, showing bounds on proof space, and establishing size-space trade-offs. This is a survey of research in proof complexity drawing on results and tools from pebbling, with a focus on proof space lower bounds and trade-offs between proof size and proof space.
Ämnesklassifikation (UKÄ) – OBLIGATORISK
|Tidskrift||Logical Methods in Computer Science|
|Status||Published - 2013 sep 13|
|Peer review utförd||Ja|