# 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. – Sasho Nikolov Sep 23 at 17:30
• Thank you, Sasho. That clears up my confusion. – Venkatesh Sep 25 at 18:23