Arithmetic Circuit Complexity
In computational complexity theory, arithmetic circuits are the standard model for computing polynomials. Informally, an arithmetic circuit takes as inputs either variables or numbers, and is allowed to either add or multiply two expression it already computed. Arithmetic circuits give us a formal way for understanding the complexity of computing polynomials. The basic type of question in this line of research is `what is the most efficient way for computing a given polynomial f?'.
Read more about Arithmetic Circuit Complexity: Definitions, Overview, Algebraic P and NP, Depth Reduction, Further Reading
Famous quotes containing the words arithmetic, circuit and/or complexity:
“Your discovery of the contradiction caused me the greatest surprise and, I would almost say, consternation, since it has shaken the basis on which I intended to build my arithmetic.... It is all the more serious since, with the loss of my rule V, not only the foundations of my arithmetic, but also the sole possible foundations of arithmetic seem to vanish.”
—Gottlob Frege (1848–1925)
“Within the circuit of this plodding life
There enter moments of an azure hue,
Untarnished fair as is the violet
Or anemone, when the spring strews them
By some meandering rivulet, which make
The best philosophy untrue that aims
But to console man for his grievances.
I have remembered when the winter came,”
—Henry David Thoreau (1817–1862)
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)