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:
“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)
“What’s the greatest enemy of Christianity to-day? Frozen meat. In the past only members of the upper classes were thoroughly sceptical, despairing, negative. Why? Among other reasons, because they were the only people who could afford to eat too much meat. Now there’s cheap Canterbury lamb and Argentine chilled beef. Even the poor can afford to poison themselves into complete scepticism and despair.”
—Aldous Huxley (1894–1963)