[Solved]: Showing that DNF VALID is coNP-hard

Problem Detail: 

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.

Asked By : user16655

Answered By : sjmc

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[1] looks good if you just want to see an answer.

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23654

 Ask a Question

 Download Related Notes/Documents