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:
- Can we say that time complexity will also be within $o(exp(n))$, where n denotes formula length?
- If 1. is true, wouldn't that prove that this problem isn't part of $P$, and, given CNF -> DNF is
NP-hardNP-complete, that $P \neq NP$? Edit: I'm aware CNF -> DNF is NP-hard, but is it NP-complete too?