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 $negvarphi$ 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
