# Network Reliability Problem

Network reliability, in which we are given an undirected graph $$G$$ with a failure probability $$p_e$$ for each edge and we are asked to calculate the probability that the network becomes disconnected due to edge failures) is known to be #P-hard. In the decision version of Network Reliability, we are given $$G$$ and a threshold $$\gamma$$ and we need to check if the probability of $$G$$ being disconnected is at most $$\gamma$$.

Since using binary search on $$\gamma$$ and the answer to the decision version, I can get arbitrarily close to the probability of $$G$$ being disconnected, can I say that the decision version is also #P-hard? The fact that I can only get close to the true value is confusing.

• The probability can be written exactly using a polynomial (in the input size) number of bits. This means that, given an algorithm for the decision version, you can get the exact value using binary search. Sep 23, 2019 at 17:30
• Thank you, Sasho. That clears up my confusion. Sep 25, 2019 at 18:23