Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-044 | 23rd April 2007 00:00

Black-White Pebbling is PSPACE-Complete

RSS-Feed




TR07-044
Authors: Philipp Hertel
Publication: 16th May 2007 14:26
Downloads: 1246
Keywords: 


Abstract:

The complexity of the Black-White Pebbling Game has remained an open problem for 30 years. It was devised to capture the power of non-deterministic space bounded computation. Since then it has been continuously studied and applied to problems in diverse areas of computer science including VLSI design and more recently propositional proof complexity. In 1983, determining its complexity was rated as "An Open Problem of the Month" in David Johnson's NP-Completeness Column. In this paper we show that the Black-White Pebbling Game is PSPACE-complete.



ISSN 1433-8092 | Imprint