to CNF efficiently

Given a Boolean Expression of length n, how to convert it into a CNF of
length m, which is a polynomial of n?
Here the length is defined as the number of variables, parenthesis pairs and
operators. CNF stands for conjunctive norm form.

In traditional conversion, the use of distribution may "double" the length,
e.g. A+BC ==> (A+B)(A+C) where A is doubled. If the length of A is much
bigger than B and C, the result has "nearly" double length. Can somebody
give a firm proof about whether the length is kept polynomial or not in the
conversion?

>From Cook's proof of NP-completeness, a Boolean expression can be
transformed into a CNF of polynomial length, but it is not intuitive.

Is there another intuitive algorithm to do so? Any reference will be
appreciated.


Thanks in advance,

Thomas Li


.

Relevant Pages

  • Re: to CNF efficiently
    ... CNF stands for conjunctive norm form. ... a Boolean expression can be ... > to transform a general Boolean formula phi into a CNF phi' such that phi ... > all logical operations with new variable names and then use CNF to state ...
    (comp.theory)
  • Re: to CNF efficiently
    ... CNF stands for conjunctive norm form. ... a Boolean expression can be ... to transform a general Boolean formula phi into a CNF phi' such that phi ... all logical operations with new variable names and then use CNF to state the ...
    (comp.theory)