1
$\begingroup$

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.

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

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).

$\endgroup$
  • $\begingroup$ 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 :) $\endgroup$ – user16655 Apr 11 '14 at 12:24
  • $\begingroup$ 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. $\endgroup$ – sjmc Apr 11 '14 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.