Complexity Classes
Many circuit complexity classes are defined in terms of class hierarchies. For each nonnegative integer i, there is a class NCi, consisting of polynomial-size circuits of depth, using bounded fan-in AND, OR, and NOT gates. We can talk about the union NC of all of these classes. By considering unbounded fan-in gates, we construct the classes ACi and AC. We construct many other circuit complexity classes with the same size and depth restrictions by allowing different sets of gates.
Read more about this topic: Circuit Complexity
Famous quotes containing the words complexity and/or classes:
“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)
“There were three classes of inhabitants who either frequent or inhabit the country which we had now entered: first, the loggers, who, for a part of the year, the winter and spring, are far the most numerous, but in the summer, except for a few explorers for timber, completely desert it; second, the few settlers I have named, the only permanent inhabitants, who live on the verge of it, and help raise supplies for the former; third, the hunters, mostly Indians, who range over it in their season.”
—Henry David Thoreau (1817–1862)