  This article presents the complexity of reachability decision problems for
parametric Markov decision processes (pMDPs), an extension to Markov decision
processes (MDPs) where transitions probabilities are described by polynomials
over a finite set of parameters. In particular, we study the complexity of
finding values for these parameters such that the induced MDP satisfies some
maximal or minimal reachability probability constraints. We discuss different
variants depending on the comparison operator in the constraints and the domain
of the parameter values. We improve all known lower bounds for this problem,
and notably provide ETR-completeness results for distinct variants of this
problem.
