  This paper investigates a series of optimization problems for one-counter
Markov decision processes (MDPs) and integer-weighted MDPs with finite state
space. Specifically, it considers problems addressing termination probabilities
and expected termination times for one-counter MDPs, as well as satisfaction
probabilities of energy objectives, conditional and partial expectations,
satisfaction probabilities of constraints on the total accumulated weight, the
computation of quantiles for the accumulated weight, and the conditional
value-at-risk for accumulated weights for integer-weighted MDPs. Although
algorithmic results are available for some special instances, the decidability
status of the decision versions of these problems is unknown in general.
  The paper demonstrates that these optimization problems are inherently
mathematically difficult by providing polynomial-time reductions from the
Positivity problem for linear recurrence sequences. This problem is a
well-known number-theoretic problem whose decidability status has been open for
decades and it is known that decidability of the Positivity problem would have
far-reaching consequences in analytic number theory. So, the reductions
presented in the paper show that an algorithmic solution to any of the
investigated problems is not possible without a major breakthrough in analytic
number theory.
  The reductions rely on the construction of MDP-gadgets that encode the
initial values and linear recurrence relations of linear recurrence sequences.
Interestingly, the reductions can also be extended to demonstrate the
Positivity-hardness of two problems that address the long-run behavior of a
system, namely the model-checking problem of frequency-LTL and the optimization
of the long-run average probability to satisfy a path property. Both of these
problems have been studied before on special instances, but are open in
general.
