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.

  • 2
    $\begingroup$ 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. $\endgroup$ Sep 23, 2019 at 17:30
  • $\begingroup$ Thank you, Sasho. That clears up my confusion. $\endgroup$
    – Venkatesh
    Sep 25, 2019 at 18:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.