  Stackelberg planning is a recently introduced single-turn two-player
adversarial planning model, where two players are acting in a joint classical
planning task, the objective of the first player being hampering the second
player from achieving its goal. This places the Stackelberg planning problem
somewhere between classical planning and general combinatorial two-player
games. But, where exactly? All investigations of Stackelberg planning so far
focused on practical aspects. We close this gap by conducting the first
theoretical complexity analysis of Stackelberg planning. We show that in
general Stackelberg planning is actually no harder than classical planning.
Under a polynomial plan-length restriction, however, Stackelberg planning is a
level higher up in the polynomial complexity hierarchy, suggesting that
compilations into classical planning come with a worst-case exponential
plan-length increase. In attempts to identify tractable fragments, we further
study its complexity under various planning task restrictions, showing that
Stackelberg planning remains intractable where classical planning is not. We
finally inspect the complexity of meta-operator verification, a problem that
has been recently connected to Stackelberg planning.
