<p>Network reliability, in which we are given an undirected graph <span class="math-container">$G$</span> with a failure probability <span class="math-container">$p_e$</span> 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 <span class="math-container">$G$</span> and a threshold <span class="math-container">$\gamma$</span> and we need to check if the probability of <span class="math-container">$G$</span> being disconnected is at most <span class="math-container">$\gamma$</span>. </p>

<p>Since using binary search on <span class="math-container">$\gamma$</span> and the answer to the decision version, I can get arbitrarily close to the probability of <span class="math-container">$G$</span> 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. </p>

CC BY-SA 4.0
2019-09-23T17:30:12.580Z
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
CC BY-SA 4.0
2019-09-25T18:23:21.973Z
Thank you, Sasho. That clears up my confusion.
Venkatesh
<graph-theory><np-hardness><counting-complexity><network-modeling><complexity-theory>
Network Reliability Problem
Venkatesh
# Network Reliability Problem

(Asked by: username_0 on 2019-09-23)

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.

**Tags:** graph-theory, np-hardness, counting-complexity, network-modeling, complexity-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: Thank you, Sasho. That clears up my confusion.  

---

## 0 answers

