  This paper discusses the complexity of graph pebbling, dealing with both
traditional pebbling and the recently introduced game of cover pebbling.
Determining whether a configuration is solvable according to either the
traditional definition or the cover pebbling definition is shown to be
NP-complete. The problem of determining the cover pebbling number for an
arbitrary demand configuration is shown to be NP-hard.
