The PSPACE-Completeness of Black-White Pebbling

Philipp Hertel, Toniann Pitassi

SIAM Journal on Computing · 2010 · 13 citations · 11 references

Concepts

Abstract

The complexity of the black-white pebbling game has remained an open problem for 30 years. In this paper we show that the black-white pebbling game is PSPACE-complete.MSC codes68-XXKeywordscomplexitypebblingPSPACE-completenessblack pebblingblack-white pebbling

References

11