COMPUTATIONAL-COMPLEXITY OF LOSS NETWORKS

In this paper we examine the theoretical limits on developing algorith ms to find blocking probabilities in a general loss network. We demons trate that exactly computing the blocking probabilities of a loss netw ork is a #P-complete problem. We also show that a general algorithm fo r approximating the blocking probabilities is also intractable unless RP=NP, which seems unlikely according to current common notions in com plexity theory. Given these results, we examine implications for desig ning practical algorithms for finding blocking probabilities in specia l cases.