A Markov decision process models the interactions between a controller giving inputs and a stochastic environment. In this well-studied model, transitions are fired instantaneously. We study semi-Markov decision processes, where each transition takes some time to fire, determined by a given probabilistic distribution (for instance, an exponential distribution). The question we investigate is how to compare two semi-Markov decision processes. We introduce and study the algorithmic complexity of two relations, “being faster than”, and “being equally fast as”.