Disjoint Products and Efficient Computation of Reliability

Abstract

In this paper, we analyze the problem of computing the probability of the union of a set of events, where each event is given as the product of a set of Boolean variables. Each Boolean variable represents the operation or failure of a particular component. The problem has direct applications to the reliability analysis of complex systems as well as more general applications. After showing that the problem is NP-hard in general, we define simple, computationally efficient procedures for generating upper and lower bounds on the required probability. We show that these procedures produce the exact answer, i.e., the upper bound equals the lower bounds, for two classes of systems, matroids and threshold systems. These results draw on the relationship between this problem and the notion of shellability studied in the context of simplicial polytopes. Shellability is shown to have a very interesting and useful interpretation in this problem setting.