  We present new algorithms for inference in credal networks --- directed
acyclic graphs associated with sets of probabilities. Credal networks are here
interpreted as encoding strong independence relations among variables. We first
present a theory of credal networks based on separately specified sets of
probabilities. We also show that inference with polytrees is NP-hard in this
setting. We then introduce new techniques that reduce the computational effort
demanded by inference, particularly in polytrees, by exploring separability of
credal sets.
