# What's wrong here, or, is CNF to DNF conversion in o(exp(n))?

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?
• 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). May 13 '15 at 21:11
• 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. May 14 '15 at 13:26
• 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... May 14 '15 at 15:55

1. Can we say that time complexity will also be within $o(exp(n))$, where $n$ denotes formula length?
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$?