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:
“I hope I may claim in the present work to have made it probable that the laws of arithmetic are analytic judgments and consequently a priori. Arithmetic thus becomes simply a development of logic, and every proposition of arithmetic a law of logic, albeit a derivative one. To apply arithmetic in the physical sciences is to bring logic to bear on observed facts; calculation becomes deduction.”
—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)