What an FPRAS is

  • Like an FPTAS, but the algorithm is randomized and may fail to produce a good solution with probability at most 1/3 19:50.

DNF formulas

  • DNF = disjunctive normal form: C₁ ∨ C₂ ∨ … ∨ C_m, where each clause Cᵢ = x_{j₁} ∧ x_{j₂} ∧ … ∧ x_{jr} (literals may be negated) 20:33, 21:16.
  • CNF flips the ANDs and ORs: an AND of clauses, each an OR of literals 21:54, 22:10.

DNF satisfiability is easy

  • A DNF is satisfiable iff at least one clause is satisfiable, so loop clause by clause; a clause is satisfiable unless it contains both x and ¬x 22:56, 23:15.
  • So DNF-SAT ∈ P, whereas CNF-SAT is NP-complete by Cook–Levin 22:10, 23:15.

DNF counting is hard

Problem: given a DNF, count the satisfying assignments 23:15.

Reduction from SAT 24:05, 25:38:

  1. Take a CNF instance φ on n variables.
  2. Negate it. By De Morgan, ¬(C₁ ∧ C₂) = ¬C₁ ∨ ¬C₂, so ¬φ is a DNF 25:38, 26:04.
  3. If ¬φ has T solutions, then φ has 2ⁿ − T solutions 26:04, 26:31.
  4. Exact counting therefore decides SAT (is the count zero or not?) 25:13, 26:31.

Complexity classification: exact DNF counting is not just NP-hard but #P-complete 26:49, 27:20.

  • The complete problem for #P is counting SAT's solutions; DNF counting is also complete for the class 27:20.
  • Intuition: NP asks whether a polynomially verifiable witness exists; #P asks how many witnesses there are — a strictly harder question, and the class contains NP 27:55, 28:21.

Why approximation is still on the table

  • The hardness proof relied on exactness — distinguishing zero from nonzero 29:02.
  • With multiplicative (1 ± ε) error you can no longer separate zero from nonzero, so the reduction breaks 29:28.
  • The answer is yes: an FPRAS exists, due to Karp, Luby and Madras (1989) 29:28, 30:14.