Probabilistic Deduction with Conditional Constraints over Basic Events
  We study the problem of probabilistic deduction with conditional constraints
over basic events. We show that globally complete probabilistic deduction with
conditional constraints over basic events is NP-hard. We then concentrate on
the special case of probabilistic deduction in conditional constraint trees. We
elaborate very efficient techniques for globally complete probabilistic
deduction. In detail, for conditional constraint trees with point
probabilities, we present a local approach to globally complete probabilistic
deduction, which runs in linear time in the size of the conditional constraint
trees. For conditional constraint trees with interval probabilities, we show
that globally complete probabilistic deduction can be done in a global approach
by solving nonlinear programs. We show 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.
