Skip to main content

Probabilistic Deduction with Conditional Constraints over Basic Events

Thomas Lukasiewicz


We show that probabilistic deduction with conditional constraints over basic events is NP-hard. We then focus on the special case of probabilistic deduction in conditional constraint trees. We elaborate very efficient and globally complete techniques for probabilistic deduction. More precisely, for exact conditional constraint trees, we present a local approach to globally complete probabilistic deduction, which runs in linear time in the size of the conditional constraint trees. For general conditional constraint trees, we show that globally complete probabilistic deduction can be done by solving global nonlinear programs. We elaborate how these nonlinear programs can be transformed into equivalent linear programs, which are solvable in polynomial time in the size of the conditional constraint trees.

Book Title
Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning‚ KR 1998‚ Trento‚ Italy‚ June 2−5‚ 1998
Anthony G. Cohn and Lenhart K. Schubert and Stuart C. Shapiro
Morgan Kaufmann