Question

DNF-SAT is the satisfiability problem for Boolean formulae in disjunctive normal form (DNF). A formula in DNF is a disjunction of anticlauses A1 ∨ A2 ∨ · · · ∨ Ak , where each Ai for 1 ≤ i ≤ k is a conjunction l1 ∧ l2 ∧···∧ lji of literals.

1. What is wrong with the following argument? CNF-SAT is polynomial-time reducible to DNF-SAT, since ∧ and ∨ each distribute over the other. For example, (x1∨x2)∧(x1∨x3) can be rewritten as (x1 ∧x1)∨(x1 ∧x3)∨(x2 ∧x1)∨(x2 ∧x3).

2. Is CNF-SAT ≤p DNF-SAT? Justify your answer.

Answer 1

1. Well, the problem is that the DNF-SAT corresponding to a given CNF-SAT can itself be exponential is size. For example,

Consider the CNF-SAT of size O(n).

(A1∨B1)∧(A2∨B2)∧⋯∧(An∨Bn)

But in DNF-SAT it turns into:

(A1∧A2∧⋯∧An)∨(B1∧A2∧⋯∧An)∨(A1∧B2∧⋯∧An)∨(B1∧B2∧⋯∧An)∨ ... (B1∧B2∧⋯∧Bn)

with $2^n$ clauses.

Due to this exponential length output, the reduction cannot be polynomial anymore.

2. No. The reason is that any reduction needs to at least output the reduced input. We have shown that the DNF-SAT output can become exponential.