<p>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.</p>

<p>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. </p>

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

<p>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$.</p>

CC BY-SA 3.0
2011-06-23T06:47:34.847Z
Nice, I like it. (In passing, in case the monotone DNF case comes up, @Robin, I believe this could be interesting: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.4716 )
Daniel Apon
CC BY-SA 3.0
2011-06-23T13:01:09.233Z
I'm not sure I understand. The minimum size CNF might be the monotone CNF formula that I already have, but I'm looking for the smallest length formula of any kind. It doesn't have to be CNF or monotone. I'll edit my question to make this clearer.
Robin Kothari
CC BY-SA 3.0
2011-06-23T13:41:54.113Z
Ah I see. Well, what I was saying covers if it has to be CNF. If it can be an arbitrary propositional formula, then I need to think more.
MGwynne
CC BY-SA 3.0
2011-06-23T06:27:50.307Z
2011-06-23T12:14:08.793Z
2011-06-23T12:14:08.793Z
MGwynne
<p>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$.  </p>

<p>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 <a href="http://en.wikipedia.org/wiki/Method_of_Four_Russians">four-Russian-like technique</a>.</p>

CC BY-SA 3.0
2011-06-23T16:16:25.037Z
Perfect, thanks! The log n factor isn't really that important to me, so this answers my question completely.
Robin Kothari
CC BY-SA 3.0
2011-06-23T13:28:43.513Z
2011-06-23T13:28:43.513Z
Noam
<p>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$.</p>

<p>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.</p>

<p>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.)</p>

<p>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)$.</p>

<p>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.</p>

<p>EDIT: I'm adding an example to make thins clearer.</p>

<p>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)$.</p>

<cc.complexity-theory><circuit-complexity><formulas>
Shortest formula for an n-term monotone CNF
Robin Kothari
# Shortest formula for an n-term monotone CNF

(Asked by: username_0 on 2011-06-22)

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)$.

**Tags:** cc.complexity-theory, circuit-complexity, formulas

---

## 2 answers

### Answer by username_3 on 2011-06-23. Score: 11 | Accepted answer

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](http://en.wikipedia.org/wiki/Method_of_Four_Russians).

> **Comments:**
> **username_0**: Perfect, thanks! The log n factor isn't really that important to me, so this answers my question completely.  

---

### Answer by username_1 on 2011-06-23. Score: 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$.

> **Comments:**
> **username_2**: Nice, I like it. (In passing, in case the monotone DNF case comes up, @Robin, I believe this could be interesting: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.4716 )  
> **username_0**: I'm not sure I understand. The minimum size CNF might be the monotone CNF formula that I already have, but I'm looking for the smallest length formula of any kind. It doesn't have to be CNF or monotone. I'll edit my question to make this clearer.  
> **username_1**: Ah I see. Well, what I was saying covers if it has to be CNF. If it can be an arbitrary propositional formula, then I need to think more.  

---

