Shortest formula for an n-term monotone CNF

Question

A monotone CNF formula with m terms on n variables ($x_1,\ldots,x_n$) is a formula of the form $f(x_1,\ldots,x_n) = \bigwedge C_i$, where each $C_i$ is an OR of some subset of the variables $x_1,\ldots,x_n$, and $i$ ranges from $1$ to $m$.

For example, $(x_1 \vee x_3 \vee x_4) \wedge (x_2 \vee x_4)$ is a monotone CNF formula with 2 terms on 4 variables.

I'm looking for the shortest formula (not necessarily monotone, not necessarily CNF, any formula will do!) on the same set of variables that represents the same function as a given monotone CNF formula on n variables with n terms. (Note that the number of terms and variables is the same.)

One obvious way to construct a formula is to expand out the given CNF definition, which will give us a formula of size $O(n^2)$. (Let's define the size of a formula to be the length of the formula when it is written down as a string.) I want to know if this is the most efficient general construction or if for every n-term monotone CNF there exists a formula of size $o(n^2)$.

I just want to know whether this is possible, I'm not really interested in an algorithm. If this is not possible, a function that serves as a counterexample would be great. Pointers to where I can find an answer in the literature are also appreciated.

EDIT: I'm adding an example to make thins clearer.

Say the input formula is $f = (x_1 \vee x_2) \wedge (x_1 \vee x_3) \wedge \ldots \wedge (x_1 \vee x_n)$. This is a monotone CNF formula. A shorter formula which represents the same function is the following: $x_1 \vee (x_2 \wedge x_3 \wedge \ldots \wedge x_n)$.

Answer 1

You can get an $\Omega(n^2/\log n)$ lower bound using a counting argument: there are $exp(n^2)$ $n$-term CNFs on $n$ variables (this is easy but requires just a little care as to make sure that there is no over-counting), but there are $exp(s \log s)$ formulae (or even circuits) of size at most $s$.

It seems that winning the last $\log n$ factor will be hard since it would require proving a quadratic lower bound on formula size, and my guess is that the few existing techniques for this don't suffice. $O(n^2/\log n)$ may even be the right answer -- at least for circuit size -- using some four-Russian-like technique.

Answer 2

Consider that for any CNF you can compute the set of prime implicates (of which any minimum must be a subset) by taking the closure under resolution, and applying subsumption elimination.

However, in the case of any monotone CNF $F$, the resolution closure of $F$ is $F$ (as there are no negative literals, there is no resolution possible). Therefore, the minimum CNF is the set of prime implicates, which is precisely the formula you already have.

Of course, I'm assuming you don't want to introduce new variables.

If you want to ensure that you have some formula which has $n$ terms, then as you suggest, the only way to get that is to expand some of the clauses by adding missing variables. Any such CNF should have the same number of literals (the size measure you suggest I believe) for a fixed $f$ and $n$.