Polynomial algorithms for estimating network reliability

We consider the problem of calculating the best possible bounds on the reliability of a system given limited information about the joint density function of its components. We show that a polynomial algorithm for this problem exists iff such an algorithm exists for a certain related problem of minimizing a linear objective function over a clutter. We give numerous examples of network as well as other problems for which the algorithm runs in polynomial time. We also use our construction to prove NP‐hardness for others.