The Computational Complexity of Probabilistic Networks

Abstract

In this thesis, the computational complexity of a number of problems related to probabilistic networks is studied that combine probabilistic inference, finding, verifying, and enumerating solutions. In particular parameter tuning, sensitivity analysis, monotonicity, enumerating solutions, and problems related to qualitative abstractions of probabilistic networks are studied. These problems are not ‘merely’ NP-hard, but are complete for a variety of complexity classes in the Counting Hierarchy (CH). It is shown that these problems often remain hard under a number of constraints on the problem structure, e.g., when the treewidth of the network is bounded. This suggests, that practical applications must restrict themselves to limited degrees of freedom (e.g. a restricted number of parameters to tune or variables to determine monotonicity constraints on) in order to be tractable. Some of the problems are complete for complexity classes that have no other ‘real world’ complete problems and may be interested also from a complexity-theoretical point of view.