VP, VNP and Algebraic Branching Programs over Min-Plus Semirings

Many problems of the above form admit polynomial-time dynamic programming (DP) algorithms. For example, Shortest $s$-$t$ Path problem can be solved in $𝒪(n^3)$ time using Bellman-Ford algorithm [1]. When edge costs are non-negative, this algorithm can be formulated as a DP. The DP table has entries $𝕋(v,\mathrm{\ell })$’s for all $v\in V(G),\mathrm{\ell }\in [n]$, where $𝕋(v,\mathrm{\ell })$ is the minimum cost of any $s$-to-$v$ path of length $\le \mathrm{\ell }$ in graph $G$, and it is computed using the recurrence $𝕋(v,\mathrm{\ell })=\underset{u\in V\left(G\right)\setminus \left\{v\right\}}{\min }\left(𝕋(u,\mathrm{\ell }-1)+\mathrm{cost}(\{u,v\})\right)$. This algorithm can also be viewed as a circuit (over ${𝖱}^{+}$) of size $𝒪(n^3)$ and depth $𝒪(n)$ as follows: For each $\mathrm{\ell }\in [n]$, the circuit has a layer consisting of gates computing $𝕋(v,\mathrm{\ell })$’s for all $v\in V(G)$. The $v^{th}$ of these gates is a $\oplus$ (i.e., min) gate which is fed outputs of gates computing $\left(𝕋(u,\mathrm{\ell }-1)+\mathrm{cost}(\{u,v\})\right)$’s for all $u\in V(G)\setminus \{v\}$. The $u^{th}$ of these gates is a $\otimes$ (i.e., $+$) gate which is fed $𝕋(u,\mathrm{\ell }-1)$ (already computed by a lower layer) and the variable $x_{\{u,v\}}$. More generally, polynomial-time pure $(\min ,+)$ DP algorithms (i.e., ones using only $\min$ and $+$ operations) can be viewed as polynomial-sized circuits over the corresponding min-plus semiring. So, lower bounds on size of $(\oplus ,\otimes )$-circuits to compute a polynomial can be viewed as lower bounds on time needed by pure $(\min ,+)$ DP algorithms to solve the corresponding problem.

In 2015, Jukna showed that the polynomials corresponding to Minimum Perfect Matching problem on bipartite graphs (i.e., Permanent polynomial) and Minimum Spanning Tree problem need $2^{\mathrm{\Omega }(n)}$ sized circuits using only $\mathrm{\infty }$ and $0$ as constants over ${𝖱}^{+}$ [10]. So, although these problems can be solved in polynomial-time using Edmond’s blossom algorithm (which works on non-bipartite graphs too) [14] and Borụvka’s or Kruskal’s or Prim’s algorithm [19, 16, 20] respectively, no pure $(\min ,+)$ DP algorithm using only $\mathrm{\infty }$ and $0$ as constants can solve them in polynomial (even sub-exponential) time over ${𝖱}^{+}$. In 1982, Jerrum and Snir showed that any circuit computing permanent needs $\ge n\cdot (2^{n-1}-1)$ many $\otimes$’s over $𝖱$ and ${𝖱}^{+}$ [9]. So, even if pure $(\min ,+)$ DP algorithms are allowed to use an unlimited number of $\min$ operations (i.e., contribution of $\min$’s to overall runtime is ignored), these algorithms remain less powerful than general algorithms.

It may be worth noting that the depth-reduction for circuits by Valiant, Skyum, Berkowitz and Rackoff [23] has a semiring independent formulation (see Theorem 51 in [10]) by Jukna.

The DP corresponding to Bellman-Ford algorithm is an incremental $(\min ,+)$ algorithm, i.e., each $+$ operation has the input cost of an edge as one of its two arguments. That is, the corresponding $(\oplus ,\otimes )$ circuit (described earlier) is skew, i.e., each $\otimes$ gate has an input variable as one of its two inputs. So, as skew circuits are equivalent to algebraic branching programs, this algorithm can be viewed as a width $𝒪(n)$ ABP (over ${𝖱}^{+}$) of size $𝒪(n^3)$ consisting of $𝒪(n)$ layers. Lower bounds on ABP size to compute a polynomial over min-plus semirings can be viewed as lower bounds on time needed by incremental $(\min ,+)$ DPs to solve the corresponding problem.

We can restrict every round/phase of the incremental DP algorithm to compute only a few (i.e., $w$) table entries using the $w$ table entries computed in the previous round. Such algorithms can be viewed as width-$w$ ABPs (i.e., ABPs wherein every layer has $\le w$ nodes) over $𝖱$ or ${𝖱}^{+}$. Over fields, it is known that constant width ABPs can be efficiently simulated using formulas (see, for example, Proposition 7.1 in [3]); the same proof also works over $𝖱$ and ${𝖱}^{+}$. So, for any constant $w\ge 1$, $w$-register incremental $(\min ,+)$ DP algorithms can be efficiently simulated using memoization-free $(\min ,+)$ DP algorithms.

In 1988, Ben-Or & Cleve also showed that width-$3$ ABPs can efficiently simulate (and so, are computationally equivalent to) formulas over fields [4]. However, their construction is such that it works with additive inverses of polynomials; so, it does not work as is over semirings $𝖱$ and ${𝖱}^{+}$.

A DP algorithm typically relies on the optimal substructure and overlapping subproblems properties of the problem to trade-off space for time. The first one says that the optimum solution of an instance can be found by combining optimum solutions for sub-instances. The second one says that the optimum solution of the same sub-instance may be needed to compute optimum solutions for multiple larger instances, and so memoization (i.e., storing its value so that it is readily available whenever needed, instead of recomputing it when needed) helps. Consider memoization-free pure $(\min ,+)$ DP algorithms, i.e., pure $(\min ,+)$ DPs wherein we restrict that the overlapping subproblems structure of the problem is not allowed to be exploited (i.e., any table entry computed in a round can be used to update only one other table entry in the next round). Such algorithms can be viewed as formulas (i.e., circuits wherein every gate has fan-out $\le 1$) over $𝖱$ or ${𝖱}^{+}$. Valiant [22] showed that ABPs can efficiently simulate formulas over fields; this proof also works over $𝖱$ and ${𝖱}^{+}$. So, incremental $(\min ,+)$ DPs can efficiently simulate memoization-free $(\min ,+)$ DPs.

In 1974, Brent showed that over rings, the depth of any formula can be reduced to logarithmic with only a polynomial size blow-up [2]. In Appendix A.3 in full version [15] of this paper, we explain how his proof can be adapted to also work over ${𝖱}^{+}$.

Jukna showed that there are polynomials that require exponential size for circuits [10] and there are polynomials computable by poly-size circuits but require super-polynomial size ABPs [11]. Mahajan, Nimbhorkar, and Tawari [17] showed lower bounds for constant-depth formulas with certain restrictions on fan-in computing the shortest path polynomial. Kluk and Nederlof [13] showed that for any $k\ge 1$, there is a graph on $k^{𝒪(1)}$ vertices such that any $(\min ,+)/(\max ,+)$ circuit computing the corresponding Independent Set (resp. Travelling Salesman and Directed Spanning Tree) polynomial needs $\mathrm{\Omega }(2^k)$ (resp. $2^{\mathrm{\Omega }(k\log \log k)}$) gates.

Our main goal is to understand the computational power of all the four models discussed in the introduction and to establish a complexity-theoretic framework to study pure algorithms for optimization problems over $(\min ,+)$ semirings.

In Section 4, we show that width-2 ABPs cannot compute $(x_1\otimes y_1)\oplus (x_2\otimes y_2)\oplus (x_3\otimes y_3)$ over $𝖱$ and ${𝖱}^{+}$. A high level description of this proof is as follows: First, we show that any ABP computing the above polynomial must have three paths, one for each monomial, such that each of these three paths contains both variables of the corresponding monomial exactly once each and no variable from the other two monomials. Then, we traverse the ABP from left-to-right and mark a layer based on the first variable occurrence amongst the edges of these three paths. Next, we traverse further to mark another layer based on the first variable occurrence amongst the edges of the remaining two paths. At this marked layer, we analyze the possible orientations of edges from the three paths entering into and exiting from it. For each possibility, we show a way to patch sub-paths from two of the three paths to form a new path; further, we analyze the possible weights of this new path and for each possibility, we show that the weight of this new path takes a value strictly lesser than the value taken by $(x_1\otimes y_1)\oplus (x_2\otimes y_2)\oplus (x_3\otimes y_3)$ for some choice of variable substitution, which is a contradiction. We make this argument precise in the proof of Theorem 3.

In Section 5, we show how to simulate any size $s$ depth $2p$ alternating $⨁⨂\mathrm{\dots }⨁⨂$ formula using a width $(2p+1)$ ABP of size $𝒪(p\cdot s)$ over $𝖱$ and ${𝖱}^{+}$. A high-level description of this proof is as follows: We associate a carefully chosen format matrix with each of the $2p$ levels of the formula. Moving bottom-to-top, we describe how to obtain width $(2p+1)$ ABPs that computes the outputs of nodes in any level $i$ (in format associated with level $i$) using the width $(2p+1)$ ABPs already built to compute outputs of nodes in level $i-1$ (in format associated with level $i-1$). We make this construction precise in the proof of Theorem 4.

In Section 6, we show that despite their non-universality, width-2 ABPs can at least compute all $\mathrm{\infty }$-$0$ (i.e., all monomials have coefficients $\mathrm{\infty }$ or $0$) bivariate polynomials over ${𝖱}^{+}$. A high level description of this proof is as follows: If a monomial has both a higher $x$ power and a higher $y$ power than another monomial, then the former monomial always (i.e., for any possible variable subsitution) takes larger values than (and so, can be safely absorbed into) the latter monomial. After such absorptions, the monomials that remain are such that the higher their $x$ powers, the lower their $y$ powers. We construct a width-2 ABP that has all $x$’s along the top level and all $y$’s along the bottom level. The two levels are joined by suitably placed bridges. Any source-to-sink path first covers up some region of the bottom level, takes a bridge to jump to the top level, and then covers up some region of the top level. The earlier it takes the bridge jump, the lower its weight’s $y$ power and higher its weight’s $x$ power. Similarly, the later it takes the bridge jump, the higher its weight’s $y$ power and lower its weight’s $x$ power. This enables us to have a path for each monomial. We make this construction idea precise in the proof of Theorem 6.

Over any field $𝔽$, suppose that we modify the definition of ${\mathrm{𝖵𝖭𝖯}}_{𝔽}$ to say that the hypercube sum’s summand is allowed to be a polynomial in the complements of hypercube variables (apart from the original variables and hypercube variables), where the complement $\overline{y}$ of any hypercube variable $y$ takes values $0$ and $1$ when $y$ takes values $1$ and $0$ respectively. However, since $\overline{y}=1-y$ for any hypercube variable $y$, this modified definition of ${\mathrm{𝖵𝖭𝖯}}_{𝔽}$ is same as its original definition. Now, let us mimic this modification over $𝖱$ and ${𝖱}^{+}$ as follows: Define ${\mathrm{𝖵𝖭𝖯}}_{𝖱(\text{or }{𝖱}^{+})}$ to consist of those $p$-families ${(f_n)}_{n\ge 1}$ for which there exists a $p$-family ${(g_n)}_{n\ge 1}\in {\mathrm{𝖵𝖯}}_{𝖱(\text{or }{𝖱}^{+})}$ and polynomials $p(n)$ & $q(n)$ such that $f_n(X)=\underset{y_1,\mathrm{\dots },y_{q\left(n\right)}\in \{\mathrm{\infty },0\}}{⨁}{g}_{p(n)}(X,y_1,\mathrm{\dots },y_{q(n)},\overline{y_1},\mathrm{\dots },\overline{y_{q(n)}})$, where the complement $\overline{y}$ of any hypercube variable $y$ takes values $\mathrm{\infty }$ and $0$ when $y$ takes values $0$ and $\mathrm{\infty }$ respectively. Unlike fields (where $\overline{y}=1-y$), $\overline{y}$ cannot be realized as a polynomial expression in $y$ over $𝖱$ and ${𝖱}^{+}$. So, it is conceivable that this modified definition may strictly strengthen the obvious definition of ${\mathrm{𝖵𝖭𝖯}}_{𝖱(\text{or }{𝖱}^{+})}$ attempted above (i.e., separate it from ${\mathrm{𝖵𝖯}}_{𝖱(\text{or }{𝖱}^{+})}$). To show that this is indeed true, we prove that the permanent family (which needs $2^{\mathrm{\Omega }(n\log n)}$ sized circuits over $𝖱$ and ${𝖱}^{+}$ [9] and so, $\notin {\mathrm{𝖵𝖯}}_{𝖱(\text{or }{𝖱}^{+})}$) satisfies this definition as follows: Recall that $per{m}_n:=\underset{\sigma \in S_n}{⨁}\underset{1\le i\le n}{⨂}{x}_{i,\sigma (i)}$. Note that every map $\sigma$ from $[n]$ to $[n]$ can be specified by a $\mathrm{\infty }$-$0$ matrix of size $n\times \log n$, where for every $1\le i\le n$, its $i^{th}$ row indicates binary encoding of $i$’s image under $\sigma$. Also, all permutations (i.e., bijective maps) correspond to those such matrices wherein all rows are distinct. So, we write

where for every $1\le t\le n$, $(t_1,\mathrm{\dots },t_{\log n})$ denotes the binary encoding of $t$, and $[\mathrm{\dots }]$ denotes the indicator function (i.e., it takes values $0$ and $\mathrm{\infty }$ when the statement enclosed within $[\mathrm{\dots }]$ is true and false respectively). Thus, we get the following expression for $per{m}_n$:

While our first attempt to define ${\mathrm{𝖵𝖭𝖯}}_{𝖱(\text{or }{𝖱}^{+})}$ allowed no hypercube variable to be complemented, the modified definition above allowed all the polynomially-many hypercube variables to be complemented. Between these two extremes, lies a spectrum of definitions based on how many hypercube variables are allowed to be complemented. For any function $r(n)$, let ${\mathrm{𝖵𝖭𝖯}}_{𝖱(\text{or }{𝖱}^{+})}^{[r(n)]}$ denote the class corresponding to the definition that allows $r(n)$ many hypercube variables to be complemented. We analyze how the relationship between ${\mathrm{𝖵𝖯}}_{𝖱(\text{or }{𝖱}^{+})}$ and ${\mathrm{𝖵𝖭𝖯}}_{𝖱(\text{or }{𝖱}^{+})}^{[r(n)]}$ changes as $r(n)$ is varied. In particular, we show the following dichotomy theorem.

First, we show that ${\mathrm{𝖵𝖯}}_{𝖱(\text{or }{𝖱}^{+})}\ne {\mathrm{𝖵𝖭𝖯}}_{𝖱(\text{or }{𝖱}^{+})}^{[r(n)]}$ when $r(n)=\omega (\log n)$ as follows: Consider the family ${(f_n)}_{n\ge 1}$ defined as $f_n:=per{m}_{\beta (n)}$, where $\beta (n)$ denotes the function for which $\beta (n)\log (\beta (n))=r(n)$. As described earlier, $per{m}_{\beta (n)}$ can be written as a hypercube sum using $\beta (n)\log (\beta (n))$ hypercube variables and their complements. Also, $per{m}_{\beta (n)}$ needs $2^{\mathrm{\Omega }\left(\beta (n)\log (\beta (n))\right)}=2^{\omega (\log n)}=n^{\omega (1)}$ sized circuits over $𝖱$ and ${𝖱}^{+}$ [9]. Therefore, ${(f_n)}_{n\ge 1}\in {\mathrm{𝖵𝖭𝖯}}_{𝖱(\text{or }{𝖱}^{+})}^{[r(n)]}\setminus {\mathrm{𝖵𝖯}}_{𝖱(\text{or }{𝖱}^{+})}$, as desired.

Next, we show that ${\mathrm{𝖵𝖯}}_{𝖱(\text{or }{𝖱}^{+})}={\mathrm{𝖵𝖭𝖯}}_{𝖱(\text{or }{𝖱}^{+})}^{[r(n)]}$ when $r(n)=𝒪(\log n)$ as follows: Consider any family ${(f_n)}_{n\ge 1}\in {\mathrm{𝖵𝖭𝖯}}_{𝖱(\text{or }{𝖱}^{+})}^{[r(n)]}$. Then, there exists a family ${(g_n)}_{n\ge 1}\in {\mathrm{𝖵𝖯}}_{𝖱(\text{or }{𝖱}^{+})}$ and polynomials $p(n)$ & $q(n)$ such that $f_n(X)=\underset{y_1,\mathrm{\dots },y_{q\left(n\right)}\in \{\mathrm{\infty },0\}}{⨁}{g}_{p(n)}(X,y_1,\mathrm{\dots },y_{q(n)},\overline{y_1},\mathrm{\dots },\overline{y_{c\log (n)}})$. Now, view $g_{p(n)}(X,y_1,\mathrm{\dots },y_{q(n)},$$\overline{y_1},\mathrm{\dots },\overline{y_{c\log (n)}})$ as a polynomial in $y_1,\mathrm{\dots },y_{q(n)},$ $\overline{y_1},\mathrm{\dots },$ $\overline{y_{c\log (n)}}$ whose coefficients are polynomials in $X$. That is, $g_{p(n)}$ is of the following form:

for some polynomials $h_{a_1,\mathrm{\dots },a_{q(n)},b_1,\mathrm{\dots },b_{c\log (n)}}$’s in $X$. Also, any summand wherein some hypercube variable and its complement both have a positive power vanishes. That is, if both $a_i$ and $b_i$ are $>0$ for some $1\le i\le c\log (n)$, then the summand evaluates to $\mathrm{\infty }$. This is because for such a summand, $y_i^{a_i}=\mathrm{\infty }$ when $y_i=\mathrm{\infty }$, and ${(\overline{y_i})}^{b_i}=\mathrm{\infty }$ when $y_i=0$. So, all such summands can be safely dropped. So, we are left with only those summands wherein for each $1\le i\le c\log (n)$, only one of $y_i$ and $\overline{y_i}$ appears. Thus, we can express $g_{p(n)}(X,y_1,\mathrm{\dots },y_{q(n)},\overline{y_1},\mathrm{\dots },\overline{y_{c\log (n)}})$ in the following form:

for some polynomials $\tilde{h}$’s in $X$, and where for each $1\le i\le c\log (n)$, ${\sigma }_i(y_i):=y_i$ when ${\sigma }_i=\text{not-comp}$, and ${\sigma }_i(y_i):=\overline{y_i}$ when ${\sigma }_i=\text{comp}$. Next, plugging the above expression of $g_{p(n)}$ in the expression of $f_n$, and then changing the order of the two summations (i.e., actually, two minimums), we get the following expression for $f_n(X)$:

Note that $A_{\underset{¯}{\sigma },\underset{¯}{\lambda }}=0$ because the summand corresponding to $y_i={\sigma }_i(0)$ for all $1\le i\le c\log (n)$ and $y_j=0$ for all $c\log (n)+1\le j\le q(n)$ is $0$; here, for each $1\le i\le c\log (n)$, ${\sigma }_i(0)$ is defined as 0 when ${\sigma }_i=$ not-comp, and $\mathrm{\infty }$ when ${\sigma }_i=$ comp. So, we get

For every $\underset{¯}{\sigma }\in {\{\text{comp, not-comp}\}}^{c\log (n)}$, let ${g_{p(n)}|}_{{\mathrm{\Phi }}_{\underset{¯}{\sigma }}}$ denote the polynomial obtained from $g_{p(n)}$ by substituting $y_i$ as ${\sigma }_i(0)$ for all $1\le i\le c\log (n)$ and $y_j$ as $0$ for all . Then, note that

Therefore, using (1) and (2), we get $f_n(X)={\underset{\underset{¯}{\sigma }}{⨁}{g}_{p(n)}|}_{{\mathrm{\Phi }}_{\underset{¯}{\sigma }}}$. So, as ${g_{p(n)}|}_{{\mathrm{\Phi }}_{\underset{¯}{\sigma }}}$ has an $n^{𝒪(1)}$ sized circuit for each $\underset{¯}{\sigma }\in {\{\text{comp, not-comp}\}}^{c\log (n)}$, it follows that $f_n(X)$ can be computed by a circuit of size $2^{c\log (n)}\cdot n^{𝒪(1)}=n^{𝒪(1)}$. Thus, we have ${(f_n)}_{n\ge 1}\in {\mathrm{𝖵𝖯}}_{𝖱(\text{or }{𝖱}^{+})}$, as desired.

The proof of $\mathrm{𝖵𝖯}\subseteq \mathrm{𝖵𝖭𝖥}$ (and so, $\mathrm{𝖵𝖭𝖯}=\mathrm{𝖵𝖭𝖥}$) over fields in [18] works almost as is over $𝖱$ and ${𝖱}^{+}$ too (explained in Appendix A.5 in full version [15] of this paper). For any $p$-family ${(f_n)}_{n\ge 1}\in {\mathrm{𝖵𝖯}}_{𝖱(\text{or }{𝖱}^{+})}$, this proof converts circuit computing $f_n$ into an equivalent polynomial-sized multiplicatively disjoint circuit $C_n$, expresses $f_n$ as the sum of values of parse trees of $C_n$, and then re-expresses this sum in terms of indicator variables (which serve as hypercube variables) to go over all subgraphs of $C_n$, using certain indicators to ensure that only the summands corresponding to parse trees survive. This gives

where ${p_v\mid }_{v\in V(C_n)}$, ${a_{(u,v)}\mid }_{(u,v)\in E(C_n)}$ are hypercube variables,

Let $\mathrm{\ell }(u)$ (respectively $r(u)$) be the left child (resp. right child) of $u$ in the circuit $C_n$.

As $B_{(u,v)}$’s, $C_u$’s, $D_u$’s, $E_u$’s and $A_u$’s have polynomial-sized formulas, so does $g_n$. In full version [15] of this paper, we show that each of these also has a polynomial-sized width-2 ABP. Then, concatenating (to get the product of) all these polynomially-many width-2 ABPs would give a polynomial-sized width-2 ABP that computes $g_n$, thereby strengthening ${\mathrm{𝖵𝖭𝖯}}_{𝖱(\text{or }{𝖱}^{+})}={\mathrm{𝖵𝖭𝖥}}_{𝖱(\text{or }{𝖱}^{+})}$ to ${\mathrm{𝖵𝖭𝖯}}_{𝖱(\text{or }{𝖱}^{+})}=\mathrm{𝖵𝖭𝖡𝖯}_{\mathrm{𝟤}}^{}{}_{𝖱(\text{or }{𝖱}^{+})}{}^{}$, where $\mathrm{𝖵𝖭𝖡𝖯}_{\mathrm{𝟤}}^{}{}_{𝖱(\text{or }{𝖱}^{+})}{}^{}$ consists of families expressible as hypercube sum over a family with polynomial-sized width-2 ABPs over $𝖱$ (or ${𝖱}^{+}$).