2
$\begingroup$

A circuit is simply a DAG, with some input wires, some output wires, and some operations on the vertices. Consider an arithmetic circuit where the only operations are addition ($+$) and multiplication ($\times$) over some ring, say, the integers modulo $N$.

Now, if I understand correctly, any circuit can be thought of as a multivariate polynomial. For instance this circuit: x 2 y \ /\ / \ / \ / * * \ / \ / + | z can be expressed by the polynomial $z = f(x,y) = 2x + 2y$. Another way of representing this polynomial is as $z = f(x,y) = 2(x+y)$, which as a circuit has less gates since it only has one addition and one multiplication.

As we saw above, by exploiting some algebraic relations like factoring the number of gates can be reduced, however, in general multivariate polynomials cannot be factored, so seeking for a factorization is not a general way of minimizing the number of operations. Also, factoring is not always the solution. For instance, consider the polynomial $f(x,y) = (2*x + y)*(2*x-y)$, which has $5$ operations. If we expand it we get $4*x*x - y*y$, which has 4, so in this case factoring does not help.

There are some other optimizations like noticing that $\underbrace{x+x+\cdots +x}_{n\text{ times}} = n\cdot x$, or $a+(b+x) = (a+b)+x$, where $a,b$ are constants (so $a+b$ does not count as an operation).

Applying all these optimizations (and many more!) to a complete circuit with many variables seem very tricky. I'm sure this is a well studied problem in computer science. My question is

Given a circuit, how do we minimize the number of gates? Are there algorithms/tools for this purpose, or is it proven to be a hard problem?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.