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)
“We are all hostages, and we are all terrorists. This circuit has replaced that other one of masters and slaves, the dominating and the dominated, the exploiters and the exploited.... It is worse than the one it replaces, but at least it liberates us from liberal nostalgia and the ruses of history.”
—Jean Baudrillard (b. 1929)
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)