# Showing that DNF VALID is coNP-hard

I'm trying to understand/show that DNF VALID is coNP-hard. I have given an algorithm for the complement of DNF VALID and shown that this is in NP (since the complement of a language in NP is in coNP), but I'm really struggling to show that DNF VALID is coNP-hard.

The complement of DNF VALID = {ϕ | ϕ is not in DNF OR ϕ is falsifiable}

A simple algorithm for the complement of DNF VALID:

On a non-deterministic TM M: "on input ϕ (boolean formula):
1. Scan through ϕ and check whether ϕ is on DNF.
If it is, accept,
if not, continue to step 2.
2. Non-deterministically choose a valuation for ϕ
3. If ϕ is falsifiable accept, if not, reject


To show that DNF VALID is coNP-hard I think that I need to show that a language that is NP-complete can be reduced in polynomial time to the complement of DNF VALID, but I'm not sure with which language to choose, and I could really use some help on how to go forth with the reduction.

• Hint: Reduce from SAT. – Yuval Filmus Apr 11 '14 at 4:42
• Which have you tried? – Raphael Apr 11 '14 at 6:48

## 1 Answer

A formula $\varphi$ in DNF is valid if and only if $\neg\varphi$ in CNF is unsatisfiable. Since CNF-SAT is NP-complete, it follows that DNF-VAL is coNP-complete. You are right that you need to show an NP-complete language can be reduced in polynomial time to the complement of DNF-VAL. Since this complement is just CNF-SAT, try reducing SAT to CNF-SAT.

There are a lot of proofs of this reduction around; this one looks good if you just want to see an answer.

 Howell, Rod. "SAT-CNF Is NP-complete." (2000).

• Thank you so much! So the negation of dnf is that it's in cnf if I have understood correctly? I will try to understand the proof :) – user16655 Apr 11 '14 at 12:24
• Right, a formula in DNF is a disjunction of conjunctions. Given the negation of such a formula, use de Morgan's laws twice to push the negation all the way to the literals, and you get a conjunction of disjunctions, i.e. a formula in CNF. – sjmc Apr 11 '14 at 13:44