Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR07-044 | 25th April 2007 00:00

Black-White Pebbling is PSPACE-Complete

RSS-Feed




Revision #2
Authors: Philipp Hertel, Toniann Pitassi
Accepted on: 25th April 2007 00:00
Downloads: 3151
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.



Changes to previous version:

System note: Fixed an error that appeared during auto-migration.


Paper:

TR07-044 | 23rd April 2007 00:00

Black-White Pebbling is PSPACE-Complete





TR07-044
Authors: Philipp Hertel
Publication: 16th May 2007 14:26
Downloads: 2964
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