Definitions
An arithmetic circuit C over the field F and the set of variables x1,...,xn is a directed acyclic graph as follows. Every node in it with indegree zero is called an input gate and is labeled by either a variable xi or a field element in F. Every other gate is labeled by either + or ; in the first case it is a sum gate and in the second a product gate. An arithmetic formula is a circuit in which every gate has outdegree one (and so the underlying graph is a directed tree).
A circuit has two complexity measures associated with it: size and depth. The size of a circuit is the number of gates in it, and the depth of a circuit is the length of the longest directed path in it. For example, the circuit in the figure has size six and depth two.
An arithmetic circuit computes a polynomial in the following natural way. An input gate computes the polynomial it is labeled by. A sum gate v computes the sum of the polynomials computed by its children (a gate u is a child of v if the directed edge (u,v) is in the graph). A product gate computes the product of the polynomials computed by its children. Consider the circuit in the figure, for example: the input gates compute (from right to left) x1,x2 and 1, the sum gates compute x1 + x2 and x2 + 1, and the product gate computes (x1 + x2) x2 (x2 + 1).
Read more about this topic: Arithmetic Circuit Complexity
Famous quotes containing the word definitions:
“Lord Byron is an exceedingly interesting person, and as such is it not to be regretted that he is a slave to the vilest and most vulgar prejudices, and as mad as the winds?
There have been many definitions of beauty in art. What is it? Beauty is what the untrained eyes consider abominable.”
—Edmond De Goncourt (1822–1896)
“The loosening, for some people, of rigid role definitions for men and women has shown that dads can be great at calming babies—if they take the time and make the effort to learn how. It’s that time and effort that not only teaches the dad how to calm the babies, but also turns him into a parent, just as the time and effort the mother puts into the babies turns her into a parent.”
—Pamela Patrick Novotny (20th century)
“What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
—G.C. (Georg Christoph)