The PSPACE-Completeness of Black-White Pebbling

DOI10.1137/080713513zbMath1218.68086OpenAlexW2083067093MaRDI QIDQ3068646

Toniann Pitassi, Philipp Hertel

Publication date: 17 January 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/a0d57fdb5fda9f3a00aea5da893fe7035a12649a

zbMATH Keywords

PSPACE-completenessspace complexitynumber of variablespebbling gameblack-white pebblingblack pebbling gamequantified SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Reversible Pebble Game on Trees ⋮ Pebbling meets coloring: reversible pebble game on trees

This page was built for publication: The PSPACE-Completeness of Black-White Pebbling