Change search
ReferencesLink to record
Permanent link

Direct link
Pebble games, proof complexity, and time-space trade-offs
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-2700-4285
2013 (English)In: Logical Methods in Computer Science, ISSN 1860-5974, Vol. 9, no 3, 15- p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2013. Vol. 9, no 3, 15- p.
Keyword [en]
CDCL, Cutting planes, DPLL, k-DNF resolution, Length, PCR, Pebble games, Pebbling formulas, Polynomial calculus, Proof complexity, Resolution, SAT solving, Separation, Space, Trade-off, Width
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-133371DOI: 10.2168/LMCS-9(3:15)2013ISI: 000327472100012ScopusID: 2-s2.0-84879808088OAI: diva2:661655
EU, FP7, Seventh Framework Programme, 279611Swedish Research Council, 621-2010-4797 621-2012-5645

QC 20131104

Available from: 2013-11-04 Created: 2013-10-31 Last updated: 2014-01-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Nordström, Jakob
By organisation
Theoretical Computer Science, TCS
In the same journal
Logical Methods in Computer Science
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 29 hits
ReferencesLink to record
Permanent link

Direct link