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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Hint: Reduce from SAT. $\endgroup$
    – Yuval Filmus
    Commented Apr 11, 2014 at 4:42
  • 1
    $\begingroup$ Which have you tried? $\endgroup$
    – Raphael
    Commented Apr 11, 2014 at 6:48

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
2
  • $\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
    Commented Apr 11, 2014 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
    Commented Apr 11, 2014 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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