Paper Info
Title
Pebble Games, Proof Complexity, and Time-Space Trade-offs.
Abstract
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.
Year
DOI
Venue
2013
10.2168/LMCS-9(3:15)2013
LOGICAL METHODS IN COMPUTER SCIENCE
Keywords
Field
DocType
Proof complexity,resolution,k-DNF resolution,polynomial calculus,PCR,cutting planes,length,width,space,trade-off,separation,pebble games,pebbling formulas,SAT solving,DPLL,CDCL
Computer-assisted proof,Discrete mathematics,Computer science,Space trade,Pebble,Proof complexity,Proof assistant,Information and Computer Science
Journal
Volume
Issue
ISSN
9
3
1860-5974
Citations 
PageRank 
References 
24
0.73
30
Authors
1
Name
Order
Citations
PageRank
Jakob Nordström117721.76