Recall that a DP algorithm is *simple* if its recursion equations only use Max
and Sum (or Min and Sum) operations. Thus, each such algorithm is, in fact, a special (recursively constructed) (max,+) circuit with fanin-2 Max and Sum gates.
Inputs for such a circuit are variables $x_1,\ldots,x_n$, where $x_i$ is the weigh given to the $i$-th ground-element. Gates are fanin-$2$ Max and Sum operations. Such a circuit solves some
maximization problem with a linear objective
function
\[
f_A(x)=\max_{a\in A}\ \skal{a,x}\,,
\]
where $A\subset\NN^n$ is a finite set of vectors of nonnegative
integers, $\NN=\{0,1,2,\ldots\}$, and $\skal{a,x}= a_1x_1+\cdots+a_nx_n$
is the scalar product. Vectors in $A$ are *feasible
solutions*. The
*size* of a circuit is the total number of gates in it.

Every (max,+) circuit (syntactically) *produces* some set $B\subset\NN^n$ of vectors as follows. At an input gate $x_i$, the singleton $\{e_i\}$ consisting of just one $0$-$1$ vector with a $1$ in the $i$-th position is produced.
If $u$ is a gate at inputs of which some sets $X,Y\subseteq \NN^n$ of vectors are produced, then the set produced at the gate $u$ is the set-theoretic union $X\cup Y$ if $u$ is
a Max gate, and is the cross-sum $X+Y=\{x+y\colon x\in X \mbox{ and } y\in Y\}$ of sets of vectors vectors, where $x+y=(x_1+y_1,\ldots,x_n+y_n)$.
The set produced by the entire circuit is the set $B\subset\NN^n$ produced at its output gate.

If a (max,+) circuit solves some maximization problem $f_A(x)$, then the produced by the circuit set $B$ of vectors needs not to coincide with $A$. We only know that $f_A(x)=f_B(x)$ must hold for all input weightings $x\in (\NN\cup\{-\infty\})^n$. If the circuit only approximates the problem $f_A$ within some factor $r$, then we only known that $ f_A(x)/r\leq f_B(x)\leq f_A(x) $ must hold for all input weightingsn $x$. Still, also in this latter case, we have some structural information about the produced set $B$.

An $r$-*shadow* of a vector $a\in\{0,1\}^n$ with $m$ ones is a vector
$b$ with at least $m/r$ ones such that $b\leq a$. A vector $b\in\NN^n$ is *contained* in a vector $a\in\NN^n$, if $b_i\leq a_i$ holds for all $i=1,\ldots,n$.

Structural Lemma:Let $A\subset \{0,1\}^n$. If $B$ is the set of vectors produced by a $(\max,+)$ circuit approximating the maximization problem $f_A$ within the factor $r$, then every vector of $B$ must be contained in at least one vector of $A$, and at least one $r$-shadow of every vector in $A$ must belong to $B$.

On the other hand, if we *know* the produced by a circuit set $B\subset\NN^n$,
then we can say how many gates the circuit must have: if $t$ is the number of gates, then the set $B$ must coverable by at most $t$ so-called ``balanced rectangle''.
This is the content of the following lemma
By a *norm-measure* we will mean any assignment of nonnegative
real numbers $\nlength{x}$ to vectors $x\in\NN^n$ such that
$\nlength{e_i}\leq 1$ for each of the $n$ unit vectors
$e_i\in\{0,1\}^n$, and the measure is subadditive in that $\nlength{x+y}\leq \nlength{x}+\nlength{y}$
holds for all $x,y\in\NN^n$. In particular, the weight of vectors
(sum of all entries) or their length (number of nonzero
positions), or their $\ell_p$-norms are norm measures.

A *rectangle* is a cross-sum $X+Y=\{x+y\colon x\in X, y\in Y\}$ of two sets of vectors $X,Y\subseteq \NN^n$. Such a rectangle is $m$-*balanced*, if every vector in $X$ has
norm between $m/3$ and $2m/3$.

Decomposition Lemma:Suppose that a set $B\subset\NN^n$ can be produced by a circuit of size $t$. Then, for every $m\geq 3$, there are at most $t$ $m$-balanced rectangles $X+Y\subseteq B$ such that every vector in $B$ of norm at least $m$ belongs to at least one of these rectangles.

Now we are ready to prove our

Design Lemma:If $\f$ is an $(n,m,l)$-design for $m\geq 3$ and $l\leq m/3r$, then any (max,+) circuit approximating the maximization problem on $\f$ within factor $r$ must have at least $|\f|$ gates.

Set $p:=m/r$. Since our circuit producing the set $B$ has size $t$, the Decomposition Lemma (with the norm of $0$-$1$ vectors being the number of $1$s) implies that there must be at most $t$ $p$-balanced rectangles $R=X+Y$ such that $R\subseteq B$ and every vector in $B$ with at least $p$ ones must belong to at least one of these rectangles. By the Structural Lemma, the set $B$ must contain at least one $r$-shadow $b_a$ of each vector $a\in A$. Since each of these $r$-shadows has at least $m/r=p$ ones, each of them must belong to at least one of these balanced rectangles, as well. So, the set $A$ can be written as a union of at most $t$ sets $A_R=\{a\in A\colon b_a\in R\}$, where each $R$ is a $p$-balanced rectangle lying in $B$. It remains therefore to show that $|A_R|\leq 1$ holds for each such rectangle $R$; then we have the desired lower bound $t\geq |A|$.

To show this, fix a vector $a\in A_R$, and let $b_a\in R$ be its $r$-shadow belonging to $R$. Since the rectangle is $p$-balanced, this means that $b_a=x+y$ for some $x\in X$ and $y\in Y$ such that the number of $1$s in $x$ lies between $p/3$ and $2p/3$. By the Structural Lemma, every vector of $x+Y$ must be contained in some vector of $A$. But all vectors in $x+Y$ contain the same vector $x$ with at least $p/3=m/3r\geq l$ ones. Since vectors in $A$ are characteristic vectors of an $(n,m,l)$-design, this means that all vectors of $x+Y$ must be contained in our fixed vector $a$. Similarly, since vector $y$ has at least $p-2p/3= p/3\geq l$ ones, all vectors of $X+y$ must be also contained in the same vector $a$. Thus, all vectors of the rectangle $R=X+Y$ must be contained in our fixed vector $a$.

Suppose now that $|A_R|\geq 2$. Then an $r$-shadow $b_c$ of some other vector $c\neq a$ of $A$ must belong to the rectangle $R$. But $b_c$ has at least $m/r>l$ ones, meaning that then $a$ and $c$ must share more than $l$ ones, a contradiction with $A$ being an $(n,m,l)$-design. Thus $|A_R|\leq 1$, as desired. $\Box$

- M. Jerrum and M. Snir, Some exact complexity results for straight-line computations over semirings, J. ACM, 29(3) (1982) 874-897. Local copy.

S. Jukna, December 2015

Go back to the comment page.