  Parametric Markov chains have been introduced as a model for families of
stochastic systems that rely on the same graph structure, but differ in the
concrete transition probabilities. The latter are specified by polynomial
constraints for the parameters. Among the tasks typically addressed in the
analysis of parametric Markov chains are (1) the computation of closed-form
solutions for reachabilty probabilities and other quantitative measures and (2)
finding symbolic representations of the set of parameter valuations for which a
given temporal logical formula holds as well as (3) the decision variant of (2)
that asks whether there exists a parameter valuation where a temporal logical
formula holds. Our contribution to (1) is to show that existing implementations
for computing rational functions for reachability probabilities or expected
costs in parametric Markov chains can be improved by using fraction-free
Gaussian elimination, a long-known technique for linear equation systems with
parametric coefficients. Our contribution to (2) and (3) is a
complexity-theoretic discussion of the model checking problem for parametric
Markov chains and probabilistic computation tree logic (PCTL) formulas. We
present an exponential-time algorithm for (2) and a PSPACE upper bound for (3).
Moreover, we identify fragments of PCTL and subclasses of parametric Markov
chains where (1) and (3) are solvable in polynomial time and establish
NP-hardness for other PCTL fragments.
