Аннотация: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 x_1,...,x_n, the circuits can also use their reciprocals 1/x_1,...,1/x_n 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 −x_1,...,−x_n. We give the same negative answer also for tropical circuits. The question of whether reciprocal inputs can substantially speed up tropical (min,+,max) circuits, using both min and max gates, remains open.
