  We consider planning problems for graphs, Markov decision processes (MDPs),
and games on graphs. While graphs represent the most basic planning model, MDPs
represent interaction with nature and games on graphs represent interaction
with an adversarial environment. We consider two planning problems where there
are k different target sets, and the problems are as follows: (a) the coverage
problem asks whether there is a plan for each individual target set, and (b)
the sequential target reachability problem asks whether the targets can be
reached in sequence. For the coverage problem, we present a linear-time
algorithm for graphs and quadratic conditional lower bound for MDPs and games
on graphs. For the sequential target problem, we present a linear-time
algorithm for graphs, a sub-quadratic algorithm for MDPs, and a quadratic
conditional lower bound for games on graphs. Our results with conditional lower
bounds establish (i) model-separation results showing that for the coverage
problem MDPs and games on graphs are harder than graphs and for the sequential
reachability problem games on graphs are harder than MDPs and graphs; (ii)
objective-separation results showing that for MDPs the coverage problem is
harder than the sequential target problem.
