2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ When you mention adding and scaling (multiplying), what field/ring are we working over? The integers ($\mathbb{Z}$)? Rational numbers ($\mathbb{Q}$)? Integers modulo $p$? Integers modulo $2$? Something else? If it is integers modulo something, did you have any particular definition of "less than" in mind? $\endgroup$ – D.W. Jan 4 '14 at 3:08
  • $\begingroup$ Also, since you mention this came from a practical problem, can you tell us anything about typical circuit sizes? About how many gates do they tend to have? About how many type-4 (conditional) gates do they tend to have? That might help us give suggestions about approaches you could try in practice, and give a sense of whether (e.g.,) SAT solvers are likely to be effective are not. $\endgroup$ – D.W. Jan 4 '14 at 3:44
  • $\begingroup$ Everything should be over the rationals. That should be sufficient, shouldn't be different than the integers. Clearly, bringing the reals into computational problems is a bad idea in general. In the practical problem, the specification isn't in terms of a circuit as I presented it here, and... well it wouldn't be concise to present. $\endgroup$ – Gilbert Bernstein Jan 6 '14 at 2:29
  • $\begingroup$ Also, I should mention that I have an NP algorithm which will probably be efficient in practice... However, I wouldn't feel ok advocating for it in a performance-sensitive context, to be safe. $\endgroup$ – Gilbert Bernstein Jan 6 '14 at 2:35
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do you know that there exists a polynomial-size witness? $\hspace{2.42 in}$ (to show that the language is in coNP) $\:$ $\endgroup$ – user6973 Jan 4 '14 at 4:43
  • $\begingroup$ Good point. The reduction works for finite fields, but I don't know if it works for $\mathbb{R}$ or $\mathbb{Q}$. For finite fields: If the circuit isn't identically zero, then by definition there exists some input that makes it produce a non-zero output. That input is the witness. The size of the witness is polynomial in the size of the circuit, since the size of each input is $O(1)$ and the number of inputs is upper-bounded by the size of the circuit. For $\mathbb{R}$ or $\mathbb{Q}$, I guess this reasoning doesn't apply, so it matters which field we're working over. $\endgroup$ – D.W. Jan 4 '14 at 4:54
  • $\begingroup$ How do you do order comparison in a finite field, in order to obtain the AND and OR gates? Finite fields don't have a natural order relation. $\endgroup$ – Niel de Beaudrap Jan 6 '14 at 7:01
  • $\begingroup$ Ahh, my mistake on the witness question. There's a trivial witness showing that the problem is in co-NP, but not a trivial witness for NP. $\endgroup$ – Gilbert Bernstein Jan 9 '14 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.