Search

It is known that the size of monotone arithmetic (+, ·) circuits can be exponentially decreased by allowing just one division “at the very end,” at the output gate. A natural question is: can the size of (+, ·) circuits be substantially reduced if we allow divisions “at the very beginning,” that is, if besides nonnegative real constants and variables x1, …, xn, the circuits can also use their reciprocals 1/x1, ..., 1/xn as inputs. We answer this question in the negative: the gain in circuit size is then always at most quadratic. Over tropical (min, +) and (max, +) semirings, division turns into subtraction; so, reciprocal inputs are then -x1, …, -xn. We give the same negative answer also for tropical circuits. The question of whether reciprocal inputs can substantially speed up tropical (min, +, max) circuits, remains open.

Many dynamic programming algorithms for discrete 0-1 optimizationproblems are "pure" in that their recursion equations only use min/max and addition operations, and do not depend on actual input weights. The well-known greedy algorithm of Kruskal solves the minimum weight spanning tree problem on $n$-vertex graphs using only $O(n^2\log n)$ operations. We prove that any pure DP algorithm for this problem must perform $2^{\Omega(\sqrt{n})}$ operations. Since the greedy algorithm can also badly fail on some optimization problems, easily solvable by pure DP algorithms, our result shows that the computational powers of these two types of algorithms are incomparable., Comment: The first structural claim of the Forest lemma (that the sets of vertices in the connected components of all forests from one side must be the same) in the previous version is just wrong. We now use entirely different arguments to prove a slightly weaker version of the numerical claim of the Forest lemma. The resulting lower bound is weaker, but still exponential