| DNF Counting |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| l | Given DNF
formula (OR of ANDs) |
||||||||||||
| (e1 Ùe2 Ù e3)
Ú (e1 Ù e4) Ú (e2 Ù e6) |
|||||||||||||
| l | Each variable
set true with probability p |
||||||||||||
| l | Estimate Pr[formula true] |
||||||||||||
| » | #P-complete |
||||||||||||
| l | [KL, KLM] FPRAS |
||||||||||||
| » | Skew to make true
outcomes “common” |
||||||||||||
| » | Time linear in
formula size |
||||||||||||
