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 current common notions in complexity theory. Given these results, we examine implications for designing practical algorithms for finding blocking probabilities in special cases.
Originally appeared in Theoretical Computer Science, vol 125, pp. 45--59, May 1994. All rights reserved by them, only for use in accordance with Theoretical Computer Science policy, etc.