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:
“Under the dominion of an idea, which possesses the minds of multitudes, as civil freedom, or the religious sentiment, the power of persons are no longer subjects of calculation. A nation of men unanimously bent on freedom, or conquest, can easily confound the arithmetic of statists, and achieve extravagant actions, out of all proportion to their means; as, the Greeks, the Saracens, the Swiss, the Americans, and the French have done.”
—Ralph Waldo Emerson (1803–1882)
“The Father and His angelic hierarchy
That made the magnitude and glory there
Stood in the circuit of a needle’s eye.”
—William Butler Yeats (1865–1939)
“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)