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)
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)