  We explore the complexity of computing the optimal pebbling number and
pebbling number of a graph. We show that deciding whether the optimal pebbling
number of G is at most k is NP-complete and deciding whether the pebbling
number of G is at most k is \Pi_2-complete. Additionally, we provide a
characterization of when an unordered set of pebbling moves can be ordered to
form a valid sequence of pebbling moves.
