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 the Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 346--353, 1994. Journal version invited to appear in the special conference issue of Journal of Computer and System Sciences, vol 53:3, pp. 317-327, December 1996. All rights reserved by them, only for use in accordance with JCSS, etc.