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