A circuit is used to express a piecewise linear function of one variable $\ f:\mathbb{Q}\to\mathbb{Q}$  The component gates are:add the outputs of two other gates togetherscale the output of one other gate by some constantoffset the output of one other gate by some constanttake as input the outputs of three other gates, labeled X, Y, C.  If C is less than some constant, output X from this gate, otherwise output YGiven such a circuit, how efficiently can one verify whether $f(x)=0$ for all $x$?My apologies that I don't have references to possibly related problems.  I tried searching piecewise linear (identity/equivalence) testing without much luck.  Randomized polynomial identity testing could possibly be tropicalized, but I don't have high hopes for that avenue of attack.Also, I should mention that this came out of a practical problem involving document layout, in case the existence of applications is motivational.Addendum:  Here is a non-standard circuit problem, which is closer to the intended application.Consider a DAG with a unique root.  Each node in the DAG represents a function of type $f:\mathbb{Q}\to\mathbb{Q}$:Leaf $\ f(w) = w\ $ This node has no children.Linear $\ f(w) = child(aw + b)\ $ This node has one child, with function $child(w)$Branch $\ f(w) = \left\{\begin{array}[ll]\\ left(w) & w < c\\ right(w) & w\geq c\end{array}\right.\ \ $  This node has two children, whose functions are $left(w)$ and $right(w)$ respectively.Then, the DAG as a whole represents a piecewise linear function, namely the composition of the atomic functions beginning at the root.  Again, the problem is to determine whether the piecewise linear function is $0$. Or, equivalently (I haven't verified the reduction works both ways) whether for two such piecewise linear functions $f=g$?
Piecewise Linear Circuit Identity Testing
ds.algorithms;linear equations;circuits