Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower bounds arguments for tropical circuits, and hence, for dynamic programs.

(1) Corrected reduction to arithmetic circuits (it holds only for multilinear polynomials, see Sect. 4), (2) added lower bounds for the depth of tropical circuits (Sect. 15), (3) give simple solution of Open Problem 3 about Min/Max gaps (Lemma 10), (4) corrected other small errors.

Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower bounds arguments for tropical circuits, and hence, for dynamic programs.