Piecewise Linear Circuit Identity Testing

Question

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 together
• scale the output of one other gate by some constant
• offset the output of one other gate by some constant
• take 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 Y

Given 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$?

Answer 1

In the general case, your problem is NP-hard, if you are working over a finite field (say, the integers modulo $p$). It is easy to see that the language of such circuits that are not identically zero is in NP (if it isn't identically zero, there exists a witness: an input that makes its output non-zero).

Also, we can reduce SAT to this problem. Consider a formula $\varphi$ in CNF, over variables $x_1,\dots,x_n$. As is standard, we'll let $1$ represent "true" and $0$ represent "false". Now it is easy to build a subcircuit that computes logical NOT ($x \mapsto 1-x$, and $1-x$ is linear), a subcircuit that computes logical OR (using your conditional gates), and a subcircuit that computes logical AND (again, using your conditional gates). Thus, we can transform $\varphi(x_1,\dots,x_n)$ to one of your circuits, where the inputs are $x_1,\dots,x_n$ and the output is the truth value of $\varphi(x_1,\dots,x_n)$. This circuit will be not identically zero if and only if $\varphi$ is satisfiable. Also, the size of this circuit is polynomial in the size of $\varphi$. Thus, if we could solve your problem in polynomial time for arbitrary circuits, then we could solve SAT in polytime and we'd have $P=NP$ -- which seems unlikely.

So, you should not expect an efficient and fully general solution to your problem, at least if you are working over a finite field.

If you are working over $\mathbb{Q}$ or $\mathbb{R}$, I don't have a proof that your problem is NP-hard (I suspect it probably still will be but I have no proof).

---

Of course, one pragmatic approach might be to try converting your problem to a SAT instance and applying an off-the-shelf SAT solver. If you are working over the integers ($\mathbb{Z}$), you might also want to try formulating it as an integer linear programming (ILP) problem and then apply an off-the-shelf ILP solver.

Depending upon the size and complexity of your circuits, this might work reasonably well in practice -- though there is no guarantee that it will always run efficiently.

---

Incidentally, your problem is equivalent to the question: "given a linear decision tree, test whether its output will be identically zero for all inputs".

The equivalence can be seen by topologically sorting the circuit so it can be computed sequentially, and then noting that it forms a decision tree: each of the first three gates can be absorbed into the linear expression, and each instance of the fourth gate corresponds to a boolean decision (testing whether some linear expression of the inputs is $\ge 0$ or not). In the subtree where this value is $<0$, you substitute in $X$ for each mention of the output of this gate; and substitute $Y$ in the subtree where this value is $>0$. The depth of the decision tree is equal to the number of type-4 gates in your circuit.

I don't know the complexity of this problem, but perhaps these search times will help you identify whether there is anything relevant in the literature.