SIAM Journal on Computing · 2010 · 13 citations · 11 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsGame TheoryAlgorithmic Game TheoryCombinatorial Game TheoryComputational ComplexityComputational Complexity ClassesRandomized ComplexityCompleteness ResultsComputational Game TheoryPebble GamesPebbling Games
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
11
Introduction to the Theory of Computation
Michael Sipser · ACM SIGACT News · 1996 · 2.8K citations
Word problems requiring exponential time(Preliminary Report)
Larry J. Stockmeyer, Albert R. Meyer · 1973 · 874 citations
The NP-completeness column: An ongoing guide
David S. Johnson · Journal of Algorithms · 1986 · 803 citations
Theory of computational complexity
Choice Reviews Online · 2001 · 229 citations
Juan Luis Esteban, Jacobo Torán · Information and Computation · 2001 · 120 citations