3
$\begingroup$

How hard is it to translate an arbitrary well-formed formula into CNF formula? It seems it can get exponential in some occasions like $(a\wedge b)\vee (c\wedge d)$ is transformed into $(a\vee c)\wedge(a\vee d)\wedge (b\vee d)\wedge (b\vee c)$, in which the size of the formula seems to expand exponentially. Therefore, I feel the problem should be in NPC. However, I do not have a clue of how to reduce this problem.

2 Answers 2