Complexity Results for Enhanced Qualitative Probabilistic Networks

While quantitative probabilistic networks (QPNs) allow experts to state influences between nodes in the network as influence signs, rather than conditional probabilities, inference in these networks often leads to ambiguous results due to unresolved trade-offs in the network. Various enhancements have been proposed that incorporate a notion of strength of the influence, such as enhanced and rich enhanced operators. Although inference in standard (i.e., not enhanced) QPNs can be done in time polynomial to the length of the input, the computational complexity of inference in these enhanced networks has not been determined yet. In this paper, we introduce relaxation schemes to relate these enhancements to the more general case where continuous influence intervals are used. We show that inference in networks with continuous influence intervals is NP-hard, and remains NP-hard when the intervals are discretised and the interval [−1, 1] is divided into blocks with length of 1 4. We discuss membership of NP, and show how these general complexity results may be used to determine the complexity of specific enhancements to QPNs. Furthermore, this might give more insight in the particular properties of feasible and infeasible approaches to enhance QPNs.