Does the naive conversion of a Boolean Formula to CNF have a polynomial or exponential complexity?
Any algorithm necessarily has exponential complexity, since the CNF of a formula can be exponentially longer than the DNF, and the input might be in DNF.