1
$\begingroup$

I've been thinking about conversion from CNF to DNF. Assume a "worst case" CNF formula with $k$ disjunctions, each containing exactly $l$ elements and no variable is used twice. Example with $k=3$ and $l=2$:

$(a \lor b) \land (c \lor d) \land (e \lor f)$

Obviously, this will result in a DNF of length $k^l$, as all possible conjunction combinations need to be listed and due to all variables being unique, nothing will vanish. Given that, computation time complexity will at least be exponential and lay in $o(k^l)$.

Now, two questions:

  1. Can we say that time complexity will also be within $o(exp(n))$, where n denotes formula length?
  2. If 1. is true, wouldn't that prove that this problem isn't part of $P$, and, given CNF -> DNF is NP-hard NP-complete, that $P \neq NP$? Edit: I'm aware CNF -> DNF is NP-hard, but is it NP-complete too?
Improve this question
$\endgroup$
2
  • $\begingroup$ For (2), note that NP-hard is not the same as NP-complete, in that NP-hardness does not actually imply that the problem is in NP. This means that the implication you give does not hold. $\endgroup$
    – Klaus Draeger
    May 14, 2015 at 13:26
  • $\begingroup$ Oh, I actually meant to say NP-complete. But after checking back, it seems to be proved that CNF -> DNF is NP-hard, but not (evidentially) NP-complete... $\endgroup$
    – Cedric Reichenbach
    May 14, 2015 at 15:55

2 Answers 2

Reset to default
5
$\begingroup$
  1. Can we say that time complexity will also be within $o(exp(n))$, where $n$ denotes formula length?

No, because no one has proven that distribution of terms is the only way to convert CNF to DNF. Obviously simple distribution of terms produces an exponential blowup in the formula size, but there may be other ways to compress the formula so that the same truth table is produced. We already known that given a truth table clever algorithms can produce smaller formulas than full disjunction over the distributed terms.

  1. If 1. is true, wouldn't that prove that this problem isn't part of $P$, and, given CNF -> DNF is NP-hard NP-complete, that $P \neq NP$?

No. If CNF to DNF conversion could be accomplished in polynomial time, its output would necessarily fit into polynomial space. Therefore you could scan this output in polynomial time and decide satisfiability. Thus P would be equivalent to NP. But if CNF to DNF conversion takes exponential time it says nothing about whether some other algorithm could efficiently solve SAT and bring P and NP together.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great answer, thanks. About the second part: I meant that if the problem requires exponential time and is NP-complete (not just hard), that it cannot be in P. But apparently, both parts of that assumption are wrong (or not proved)... $\endgroup$
    – Cedric Reichenbach
    May 15, 2015 at 9:53
2
$\begingroup$

  1. The conversion of CNF to DNF is exponential in the worst case. There are no tricks that avoid writing out an exponential number of clauses. It is not obvious to me that the little-o notation with exp is correct, but, yes, it is exponential.

  2. No. The NP-complete satisfiability problem you are thinking of is a decision problem, a yes or no answer, for whether or not there is at least one solution, a satisfying assignment of truth values. In your example, each clause of the resulting DNF corresponds to a solution; thus, this conversion is equivalent to listing all solutions, a lot more work than just identifying one. So, you can't assume that CNF-to-DNF conversion is NP-complete.

Improve this answer
$\endgroup$

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.