Pebble games, proof complexity, and time-space trade-offs
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Pebble games, proof complexity, and time-space trade-offs. / Nordström, Jakob.
In: Logical Methods in Computer Science, Vol. 9, No. 3, 15, 13.09.2013.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Pebble games, proof complexity, and time-space trade-offs
AU - Nordström, Jakob
PY - 2013/9/13
Y1 - 2013/9/13
N2 - 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.
AB - 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.
KW - CDCL
KW - Cutting planes
KW - DPLL
KW - k-DNF resolution
KW - Length
KW - PCR
KW - Pebble games
KW - Pebbling formulas
KW - Polynomial calculus
KW - Proof complexity
KW - Resolution
KW - SAT solving
KW - Separation
KW - Space
KW - Trade-off
KW - Width
UR - http://www.scopus.com/inward/record.url?scp=84879808088&partnerID=8YFLogxK
U2 - 10.2168/LMCS-9(3:15)2013
DO - 10.2168/LMCS-9(3:15)2013
M3 - Journal article
AN - SCOPUS:84879808088
VL - 9
JO - Logical Methods in Computer Science
JF - Logical Methods in Computer Science
SN - 1860-5974
IS - 3
M1 - 15
ER -
ID: 251870251