On the Relative Strength of Pebbling and Resolution

DOI10.1145/2159531.2159538zbMath1352.03069arXiv1003.3047OpenAlexW1985970833MaRDI QIDQ2946664

Jakob Nordström

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1003.3047

zbMATH Keywords

resolutiontrade-offproof complexityspace lower boundspebble gamespebbling formula

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (5)

Static-memory-hard functions, and modeling the cost of space vs. time ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ An Introduction to Lower Bounds on Resolution Proof Systems ⋮ Reversible pebble games and the relation between tree-like and general resolution space ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling

This page was built for publication: On the Relative Strength of Pebbling and Resolution