Solution

An exponential increase is unavoidable for an equivalent conjunctive normal form over the original variables. Consider the linear-size Boolean formula

F_{n} = ⋁_{i = 1}^{n} (p_{i} \land q_{i}) .

Distributing gives the

2^{n}

F_{n} \equiv ⋀_{(r_{1}, \dots, r_{n}) \in {p_{1}, q_{1}} \times \dots \times {p_{n}, q_{n}}} (r_{1} \lor \dots \lor r_{n}) .

To prove that the growth is necessary, fix one choice

r_{i} \in {p_{i}, q_{i}}

. Let

α_{r}

make every

r_{i}

false and its partner true. Each pair then contains a false variable, so

F_{n}

is false. Any equivalent conjunctive normal form must contain a Boolean clause

C

falsified by

α_{r}

and entailed by

F_{n}

Every individual term

p_{i} \land q_{i}

entails

C

, because that term implies

F_{n}

. After tautological Boolean clauses are discarded, this forces

C

to contain a positive

p_{i}

or positive

q_{i}

for every

i

: otherwise set both variables in that pair true and independently falsify all Boolean literals of

C

, contradicting the entailment. Since

C

is false at

α_{r}

, it must contain the false member

r_{i}

, never its true partner. Consequently the same

C

cannot be false at any different

α_{s}

. The

2^{n}

different assignments therefore require at least

2^{n}

Writing the answer already takes

Ω (2^{n}) time in the worst case

. This obstruction applies to first-order logic as well, since the example can be expressed using ground unary atomic formulas. It concerns exact equivalence without auxiliary symbols. A Tseytin transformation can produce a polynomial-size equisatisfiable conjunctive normal form with auxiliary variables, so the statement must not be extended to that different task.

 Ancestors (12)

There are no discussions about this article yet.

There are currently no matching articles.