Record number :
1182527
Title of article :
Complexity results for enhanced qualitative probabilistic networks Original Research Article
Author/Authors :
Johan Kwisthout، نويسنده , , Gerard Tel، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2008
Pages :
10
From page :
879
To page :
888
Abstract :
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 image. 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.
Keywords :
Qualitative probabilistic networks , Complexity of reasoning , Enhanced networks , NP-complete , Gadget , Bayesian networks
Journal title :
International Journal of Approximate Reasoning
Link To Document :