Theoretical Computer Science 125 (1994), 45-59.
In this paper we examine the theoretical limits on developing algorithms to find blocking probabilities in a general loss network. We demonstrate that exactly computing the blocking probabilities of a loss network is a #P-complete problem. We also show that a general algorithm for approximating the blocking probabilities is also intractable unless RP=NP, which seems unlikely according to common notions in complexity theory. Given these results, we examine implications for designing practical algorithms for finding blocking probabilities in special cases.