| Reliability Connection |
|
|
|
|
|
|
|
|
|
|
| l | Reliability as
DNF counting: |
||||||||
| » | Variable per
edge, true if edge fails |
||||||||
| » | Cut fails if all
edges do (AND of edge vars) |
||||||||
| » | Graph fails if
some cut does (OR of cuts) |
||||||||
| » | FAIL(p)=Pr[formula
true] |
||||||||
| Problem:
the DNF has 2n clauses |
