\(
\def\<#1>{\left<#1\right>}
\let\geq\geqslant
\let\leq\leqslant
% an undirected version of \rightarrow:
\newcommand{\mathdash}{\relbar\mkern-9mu\relbar}
\def\deg#1{\mathrm{deg}(#1)}
\newcommand{\dg}[1]{d_{#1}}
\newcommand{\Norm}{\mathrm{N}}
\newcommand{\const}[1]{c_{#1}}
\newcommand{\cconst}[1]{\alpha_{#1}}
\newcommand{\Exp}[1]{E_{#1}}
\newcommand*{\ppr}{\mathbin{\ensuremath{\otimes}}}
\newcommand*{\su}{\mathbin{\ensuremath{\oplus}}}
\newcommand{\nulis}{\mathtt{0}} %{\vmathbb{0}} %
\newcommand{\vienas}{\mathtt{1}} %{\vmathbb{1}}
\newcommand{\Up}[1]{#1^{\uparrow}} %{#1^{\vartriangle}}
\newcommand{\Down}[1]{#1^{\downarrow}} %{#1^{\triangledown}}
\newcommand{\lant}[1]{#1_{\mathrm{la}}} % lower antichain
\newcommand{\uant}[1]{#1_{\mathrm{ua}}} % upper antichain
\newcommand{\skal}[1]{\langle #1\rangle}
\newcommand{\NN}{\mathbb{N}} % natural numbers
\newcommand{\RR}{\mathbb{R}}
\newcommand{\minTrop}{\mathbb{T}_{\mbox{\rm\footnotesize min}}}
\newcommand{\maxTrop}{\mathbb{T}_{\mbox{\rm\footnotesize max}}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\pRR}{\mathbb{R}_{\mbox{\tiny $+$}}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\gf}[1]{GF(#1)}
\newcommand{\conv}[1]{\mathrm{Conv}(#1)}
\newcommand{\vvec}[2]{\vec{#1}_{#2}}
\newcommand{\f}{{\mathcal F}}
\newcommand{\h}{{\mathcal H}}
\newcommand{\A}{{\mathcal A}}
\newcommand{\B}{{\mathcal B}}
\newcommand{\C}{{\mathcal C}}
\newcommand{\R}{{\mathcal R}}
\newcommand{\MPS}[1]{f_{#1}} % matrix multiplication
\newcommand{\ddeg}[2]{\#_{#2}(#1)}
\newcommand{\length}[1]{|#1|}
\DeclareMathOperator{\support}{sup}
\newcommand{\supp}[1]{\support(#1)}
\DeclareMathOperator{\Support}{sup}
\newcommand{\spp}{\Support}
\newcommand{\Supp}[1]{\mathrm{Sup}(#1)} %{\mathcal{S}_{#1}}
\newcommand{\lenv}[1]{\lfloor #1\rfloor}
\newcommand{\henv}[1]{\lceil#1\rceil}
\newcommand{\homm}[2]{{#1}^{\langle #2\rangle}}
\let\daug\odot
\let\suma\oplus
\newcommand{\compl}[1]{Y_{#1}}
\newcommand{\pr}[1]{X_{#1}}
\newcommand{\xcompl}[1]{Y'_{#1}}
\newcommand{\xpr}[1]{X'_{#1}}
\newcommand{\cont}[1]{A_{#1}} % content
\def\fontas#1{\mathsf{#1}} %{\mathrm{#1}} %{\mathtt{#1}} %
\newcommand{\arithm}[1]{\fontas{Arith}(#1)}
\newcommand{\Bool}[1]{\fontas{Bool}(#1)}
\newcommand{\linBool}[1]{\fontas{Bool}_{\mathrm{lin}}(#1)}
\newcommand{\rBool}[2]{\fontas{Bool}_{#2}(#1)}
\newcommand{\BBool}[2]{\fontas{Bool}_{#2}(#1)}
\newcommand{\MMin}[1]{\fontas{Min}(#1)}
\newcommand{\MMax}[1]{\fontas{Max}(#1)}
\newcommand{\infMax}[1]{\fontas{Max}_{-\infty}(#1)}
\newcommand{\negMin}[1]{\fontas{Min}^{-}(#1)}
\newcommand{\negMax}[1]{\fontas{Max}^{-}(#1)}
\newcommand{\Min}[2]{\fontas{Min}_{#2}(#1)}
\newcommand{\Max}[2]{\fontas{Max}_{#2}(#1)}
\newcommand{\convUn}[1]{\fontas{L}_{\ast}(#1)}
\newcommand{\Un}[1]{\fontas{L}(#1)}
\newcommand{\kUn}[2]{\fontas{L}_{#2}(#1)}
\newcommand{\Nor}{\mu} % norm without argument
\newcommand{\nor}[1]{\Nor(#1)}
\newcommand{\bool}[1]{\hat{#1}} % Boolean version of f
\newcommand{\bphi}{\phi} % boolean circuit
\newcommand{\xf}{\boldsymbol{\mathcal{F}}}
\newcommand{\euler}{\mathrm{e}}
\newcommand{\ee}{f} % other element
\newcommand{\exchange}[3]{{#1}-{#2}+{#3}}
\newcommand{\dist}[2]{{#2}[#1]}
\newcommand{\Dist}[1]{\mathrm{dist}(#1)}
\newcommand{\mdist}[2]{\dist{#1}{#2}} % min-max dist.
\newcommand{\matching}{\mathcal{M}}
\renewcommand{\E}{A}
\newcommand{\F}{\mathcal{F}}
\newcommand{\set}{W}
\newcommand{\Deg}[1]{\mathrm{deg}(#1)}
\newcommand{\mtree}{MST}
\newcommand{\stree}{{\cal T}}
\newcommand{\dstree}{\vec{\cal T}}
\newcommand{\Rich}{U_0}
\newcommand{\Prob}[1]{\ensuremath{\mathrm{Pr}\left\{{#1}\right\}}}
\newcommand{\xI}{\boldsymbol{I}}
\newcommand{\plus}{\mbox{\tiny $+$}}
\newcommand{\sgn}[1]{\left[#1\right]}
\newcommand{\ccompl}[1]{{#1}^*}
\newcommand{\contr}[1]{[#1]}
\newcommand{\harm}[2]{{#1}\,\#\,{#2}} %{{#1}\,\oplus\,{#2}}
\newcommand{\hharm}{\#} %{\oplus}
\newcommand{\rec}[1]{1/#1}
\newcommand{\rrec}[1]{{#1}^{-1}}
\DeclareRobustCommand{\bigO}{%
\text{\usefont{OMS}{cmsy}{m}{n}O}}
\newcommand{\dalyba}{/}%{\oslash}
\newcommand{\mmax}{\mbox{\tiny $\max$}}
\newcommand{\thr}[2]{\mathrm{Th}^{#1}_{#2}}
\newcommand{\rectbound}{h}
\newcommand{\pol}[3]{\sum_{#1\in #2}{#3}_{#1}\prod_{i=1}^n x_i^{#1_i}}
\newcommand{\tpol}[2]{\min_{#1\in #2}\left\{\skal{#1,x}+\const{#1}\right\}}
\newcommand{\comp}{\circ} % composition
\newcommand{\0}{\vec{0}}
\newcommand{\drops}[1]{\tau(#1)}
\newcommand{\HY}[2]{F^{#2}_{#1}}
\newcommand{\hy}[1]{f_{#1}}
\newcommand{\hh}{h}
\newcommand{\hymin}[1]{f_{#1}^{\mathrm{min}}}
\newcommand{\hymax}[1]{f_{#1}^{\mathrm{max}}}
\newcommand{\ebound}[2]{\partial_{#2}(#1)}
\newcommand{\Lpure}{L_{\mathrm{pure}}}
\newcommand{\Vpure}{V_{\mathrm{pure}}}
\newcommand{\Lred}{L_1} %L_{\mathrm{red}}}
\newcommand{\Lblue}{L_0} %{L_{\mathrm{blue}}}
\newcommand{\epr}[1]{z_{#1}}
\newcommand{\wCut}[1]{w(#1)}
\newcommand{\cut}[2]{w_{#2}(#1)}
\newcommand{\Length}[1]{l(#1)}
\newcommand{\Sup}[1]{\mathrm{Sup}(#1)}
\newcommand{\ddist}[1]{d_{#1}}
\newcommand{\sym}[2]{S_{#1,#2}}
\newcommand{\minsum}[2]{\mathrm{MinS}^{#1}_{#2}}
\newcommand{\maxsum}[2]{\mathrm{MaxS}^{#1}_{#2}} % top k-of-n function
\newcommand{\cirsel}[2]{\Phi^{#1}_{#2}} % its circuit
\newcommand{\sel}[2]{\sym{#1}{#2}} % symmetric pol.
\newcommand{\cf}[1]{{#1}^{o}}
\newcommand{\Item}[1]{\item[\mbox{\rm (#1)}]} % item in roman
\newcommand{\bbar}[1]{\underline{#1}}
\newcommand{\Narrow}[1]{\mathrm{Narrow}(#1)}
\newcommand{\Wide}[1]{\mathrm{Wide}(#1)}
\newcommand{\eepsil}{\varepsilon}
\newcommand{\amir}{\varphi}
\newcommand{\mon}[1]{\mathrm{mon}(#1)}
\newcommand{\mmon}{\alpha}
\newcommand{\gmon}{\alpha}
\newcommand{\hmon}{\beta}
\newcommand{\nnor}[1]{\|#1\|}
\newcommand{\inorm}[1]{\left\|#1\right\|_{\mbox{\tiny $\infty$}}}
\newcommand{\mstbound}{\gamma}
\newcommand{\coset}[1]{\textup{co-}{#1}}
\newcommand{\spol}[1]{\mathrm{ST}_{#1}}
\newcommand{\cayley}[1]{\mathrm{C}_{#1}}
\newcommand{\SQUARE}[1]{\mathrm{SQ}_{#1}}
\newcommand{\STCONN}[1]{\mathrm{STCON}_{#1}}
\newcommand{\STPATH}[1]{\mathrm{PATH}_{#1}}
\newcommand{\SSSP}[1]{\mathrm{SSSP}(#1)}
\newcommand{\APSP}[1]{\mathrm{APSP}(#1)}
\newcommand{\MP}[1]{\mathrm{MP}_{#1}}
\newcommand{\CONN}[1]{\mathrm{CONN}_{#1}}
\newcommand{\PERM}[1]{\mathrm{PER}_{#1}}
\newcommand{\mst}[2]{\tau_{#1}(#2)}
\newcommand{\MST}[1]{\mathrm{MST}_{#1}}
\newcommand{\MIS}{\mathrm{MIS}}
\newcommand{\dtree}{\mathrm{DST}}
\newcommand{\DST}[1]{\dtree_{#1}}
\newcommand{\CLIQUE}[2]{\mathrm{CL}_{#1,#2}}
\newcommand{\ISOL}[1]{\mathrm{ISOL}_{#1}}
\newcommand{\POL}[1]{\mathrm{POL}_{#1}}
\newcommand{\ST}[1]{\ptree_{#1}}
\newcommand{\Per}[1]{\mathrm{per}_{#1}}
\newcommand{\PM}{\mathrm{PM}}
\newcommand{\error}{\epsilon}
\newcommand{\PI}[1]{A_{#1}}
\newcommand{\Low}[1]{A_{#1}}
\newcommand{\node}[1]{v_{#1}}
\newcommand{\BF}[2]{W_{#2}[#1]} % Bellman-Ford
\newcommand{\FW}[3]{W_{#1}[#2,#3]} % Floyd-Washall
\newcommand{\HK}[1]{W[#1]} % Held-Karp
\newcommand{\WW}[1]{W[#1]}
\newcommand{\pWW}[1]{W^{+}[#1]}
\newcommand{\nWW}[1]{W^-[#1]}
\newcommand{\knap}[2]{W_{#2}[#1]}
\newcommand{\Cut}[1]{w(#1)}
\newcommand{\size}[1]{\mathrm{size}(#1)}
\newcommand{\dual}[1]{{#1}^{\ast}}
\def\gcd#1{\mathrm{gcd}(#1)}
\newcommand{\econt}[1]{C_{#1}}
\newcommand{\xecont}[1]{C_{#1}'}
\newcommand{\rUn}[1]{\fontas{L}_{r}(#1)}
\newcommand{\copath}{\mathrm{co}\text{-}\mathrm{Path}_n}
\newcommand{\Path}{\mathrm{Path}_n}
\newcommand{\uup}[1]{\overline{#1}}
\newcommand{\up}[1]{\overline{#1}}
\newcommand{\coset}[1]{\mathrm{1\hspace{-0.1em}-}{#1}} %{{#1}^*}
\)
Boolean bounds for (max,+) circuits
-
For a set $A\subseteq\{0,1\}^n$ of vectors, let (as in the book)
$\Bool{A}$
denote the minimum size of a monotone Boolean $(\lor,\land)$ circuit computing the Boolean function $g(x)=\bigvee_{a\in A}\bigwedge_{i : a_i\neq 0}x_i$. That is, for every input $x\in\{0,1\}^n$, $f(x)=1$ iff $x\geq a$ for some $a\in A$. Also, $\MMax{A}$ denotes the minimum size of a tropical $(\max,+)$ circuit solving the maximization problem $f(x)=\max_{a\in A}\skal{a,x}$ on the set $A$ of feasible solutions.
As Lemma 4.1(1) in the book shows,
$\MMin{A}\geq \Bool{A}$ holds for $(\min,+)$ circuits solving the minimization problem on any set $A\subseteq\NN^n$ of feasible solution.
This Boolean lower bound holds even for approximating $(\min,+)$ circuits and even for $(\min,\max,+)$ circuits (when also $\max$ gates are allowed to be used).
-
But the argument used in the proof of Lemma 4.1 does not work
for $(\min,\max,+)$ circuits, and even for $(\max,+)$ circuits, exactly solving or approximating maximization problems $f(x)=\max_{a\in A}\skal{a,x}$, because
then the signum $\sgn{f(x)}$ of $f(x)$ (which is defined to be $0$ if $f(x)=0$, and $1$ if $f(x)\gt 0$) is just the OR of all variables, so that the resulting (dual) circuit does not compute the Boolean version $g(x)=\bigvee_{a\in A}\bigwedge_{i\in \supp{a}}x_i$ of $f$, unless $A=\{\vec{1}\}$: this holds because both $\sgn{\max(x,y)}$ and
$\sgn{x+y}$ are equal to the OR $\sgn{x}\lor\sgn{y}$.
Still, we have the following lower bound in terms of "complementary" sets.
Theorem A: Let $A\subseteq\{0,1\}^n$ and $\coset{A}:=\{\vec{1}-a\colon a\in A\}$.
There is an absolute constant $c\gt 0$ such that
\begin{equation}\label{eq:bool1}
\MMax{A}
\geq \sqrt{\frac{1}{cn}\cdot \Bool{\coset{A}}}-n
\,.
\end{equation}
Proof:
Let $s:=\MMax{A}$ and $t:=\MMin{\coset{A}}$.
As shown in Corollary 6.14(2), $t$ is at most a constant times $n(n+s)^2$ from which $(n+s)^2\geq t/cn$ and, hence, $s\geq \sqrt{t/cn}-n$ follows. Since, by Lemma 4.1(1), $\Bool{\coset{A}}\leq t$ holds, the desired lower bound \eqref{eq:bool1} on
$\MMax{A}=s$ follows, as well.
∎
The Boolean bound on $\MMax{A}$ holds also in terms of $\Bool{A}$
(the same set $A$) if the $(\max,+)$ circuits must correctly solve the maximization problem on the set $A$ not only for all
input weightings $x\in\RR_+^n$ but for all input weightings $x\in(\RR_+\cup\{-\infty\})^n$; that is, now $-\infty$ is also among possible input weights. Let
$\infMax{A}$ denote the corresponding complexity measure. Note that
we always have $\infMax{A}\geq \MMax{A}$. Our goal is to prove
a lower bound $\infMax{A}\geq \Bool{A}$. This is a direct consequence of the following "folklore" relation (given by Lemma A below) between circuits over any semiring of zero characteristic and monotone Boolean circuits.
Consider circuits over (commutative) semirings $(R,\suma,\daug,\nulis,\vienas)$ that, besides a multiplicative identity element $\vienas$ (with
$x\daug\vienas=x$) also contain an additive identity element $\nulis$ with
$x\suma\nulis=x$ and $x\daug\nulis=\nulis$.
Such a semiring is
of zero
characteristic if $\vienas\suma\vienas \suma \cdots \suma \vienas\neq
\nulis$ holds for any finite sum of the multiplicative
identity element $\vienas$.
-
Note that polynomials $ f(x)=\sum_{a\in A}\ \prod_{i=1}^n x_i^{a_i}$ over such
semirings have the following property: on every input
$x\in\{\nulis,\vienas\}^n$ (consisting of identity elements), we have $f(x)\neq \nulis$ if and only if
there is a vector $a\in A$ such that $x$ has the multiplicative identity
element $\vienas$ in all positions $i$ where $a_i\neq 0$. This happens
precisely when the Boolean version $g(x)= \bigvee_{a\in A} \bigwedge_{i\in \supp{a}}x_i$ accepts the
corresponding Boolean version of $x$ (with additive identity element $\nulis$ replaced
with $0$, and the multiplicative identity element $\vienas$ replaced by $1$). That is, when restricted to only inputs in $\{\nulis,\vienas\}^n$ (vectors of identity elements), the decision
version of a polynomial $f$ captures the behavior of $f$. This
observation gives an idea behind the following "folklore" lower bound.
Recall that a circuit over a semiring $(R,\suma,\daug,\nulis,\vienas)$
is constant-free if no semiring elements $c\in R$ are used as inputs
(hence, the variables $x_1,\ldots,x_n$ are the only inputs).
The Boolean version of such a circuit is obtained by replacing
each ``addition'' gate $u\suma v$ by an OR gate $u\lor v$, and each
``multiplication'' gate $u\daug v$ by an AND gate $u\land v$.
Lemma A (Folklore): If a constant-free circuit $\Phi$ over a semiring $(R,\suma,\daug,\nulis,\vienas)$ of zero characteristic
computes a polynomial $f$, then the Boolean version of $\Phi$ computes the
Boolean version of $f$.
Proof:
Consider the set $S=\{\up{n}\colon n\in\NN\}\subseteq R$ of semiring
elements, where $\uup{n}:=\nulis$ (the additive identity element) for $n=0$, and
$\uup{n}:=\vienas\suma \cdots \suma \vienas$ is the $n$-fold sum of the
multiplicative unity $\vienas$ for all $n\geq 1$. Since $\uup{n}\suma
\uup{m}=\uup{n+m}$ and $\uup{n}\daug \uup{m}=\uup{n\cdot m}$, the set $S$
is closed under both semiring operations. So,
$(S,\suma,\daug,\nulis,\vienas)$ is a subsemiring of $R$. This implies
that when we restrict the circuit $\Phi$ to take inputs only from
$\{\nulis,\vienas\}^n$, all intermediate results computed at the gates of $\Phi$
belong to $S$. Here, we use the fact that the original
circuit $\Phi$ was constant-free, that is, has not
used any semiring elements as (constant) inputs.
Consider the mapping $h:S\to\{0,1\}$
given by $h(\nulis):=0$ and $h(\uup{n}):=1$ for all $n\geq 1$. Since
$R$ has zero-characteristic, $\uup{n}=\nulis$ holds if and only if
$n=0$. Thus, $h(x\suma y)=h(x)\lor h(y)$ and $h(x\daug
y)=h(x)\land h(y)$ hold for all $x,y\in S$, meaning that
the mapping $h$ is a homomorphism from the semiring
$(S,\suma,\daug,\nulis,\vienas)$ to the Boolean semiring
$(\{0,1\},\lor,\land,0,1)$. So, since the circuit
$\Phi$ computes the polynomial $f$ correctly on all inputs in
$\{\nulis,\vienas\}^n$, the Boolean version of the circuit $\Phi$ correctly computes the
decision version of $f$ on all (Boolean) inputs in
$\{0,1\}^n$.
∎
Theorem B: For every finite set $A\subseteq\NN^n$, we have
$\infMax{A}\geq \Bool{A}$.
Proof:
Let $\Phi$ be a $(\max,+)$ circuit solving the maximization problem $f(x)=\max_{a\in
A}\ \skal{a,x}$ on $A$ for all input weightings $x\in(\RR_+\cup\{-\infty\})^n$.
We can assume that the circuit $\Phi$ is constant-free: if $g(x)=\max_{b\in
B}\ \skal{b,x}+\const{b}$ is the $(\max,+)$ polynomial produced by the circuit $\Phi$, then $\const{b}=0$ for all $b\in B$, because $\const{b}\in\RR_+$ and $g(\vec{0})=f(\vec{0})=0$.
In our case the underlying semiring is
$(R,\suma,\daug,\nulis,\vienas)$
with $R=\RR_+\cup\{-\infty\}$, $x\suma y = \max(x,y)$, $x\daug y = x+y$,
$\nulis=-\infty$ and $\vienas=0$. This semiring is of zero characteristic because $0+\cdots +0\neq -\infty$. Hence, it remains to apply Lemma A.
∎
Footnotes:
(1)
Lemma 4.1: Let $A\subseteq\NN^n$ be any finite set of vectors. Every
$(\min,\max,+)$ circuit approximating the minimization problem
$f(x)=\min_{a\in A}\sum_{i=1}^na_ix_i$ on
$A$ within a finite factor $r=r(n)\geq 1$ must have at least
$\Bool{A}$ gates.
Jump back ☝
(2)
Jump back ☝
⇦ Back to the comments page