If A is a formula and B is its Negation Normal Form , then are A and B about the same size or is there no relationship between the sizes of A and B?

Question

All the details in the title. I think that they are about the same size (to a multiplicative constant). Am I right?

Other options include:

$3)$ $A$ is much larger than $B$

$4)$ $B$ is much larger than $A$

All details should be in the body – Hagen von Eitzen Jul 18 '20 at 16:43 — Hagen von Eitzen, Jul 18 '20 at 16:43

score 0 · Answer 1 · answered Jul 18 '20 at 16:49

0

I don't think so. The formula $$ (\cdots((p_1\leftrightarrow p_2)\leftrightarrow p_3)\cdots)\leftrightarrow p_n$$ has length $O(n)$, whereas its Negation Normal Form should be of length $\Theta( 2^n)$.

answered Jul 18 '20 at 16:49

Hagen von Eitzen

374,180

If A is a formula and B is its Negation Normal Form , then are A and B about the same size or is there no relationship between the sizes of A and B?

1 Answers1