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$
3
  • $\begingroup$ This question does not appear to be a research-level question, and will probably continue to attract down-votes and close-votes. It will be a better fit for CS.SE, where non-research questions are encouraged; if you want then I can migrate it for you (please don't cross-post; just ping me in the comments or flag). $\endgroup$
    – Artem Kaznatcheev
    May 13 '15 at 21:11
  • $\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 '15 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 '15 at 15:55
4
$\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 '15 at 9:53

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.