The Computational Complexity of Sensitivity Analysis and Parameter
  Tuning
  While known algorithms for sensitivity analysis and parameter tuning in
probabilistic networks have a running time that is exponential in the size of
the network, the exact computational complexity of these problems has not been
established as yet. In this paper we study several variants of the tuning
problem and show that these problems are NPPP-complete in general. We further
show that the problems remain NP-complete or PP-complete, for a number of
restricted variants. These complexity results provide insight in whether or not
recent achievements in sensitivity analysis and tuning can be extended to more
general, practicable methods.
