AbstractBoolean circuits were introduced in complexity theory to provide a model for parallel computation. A big advantage of studying Boolean circuits is that they can be viewed as simple combinatorial objects and thus allow us to use many algebraic and combinatorial techniques to derive upper and lower bounds on their computational power. The relationship between Boolean circuits and the traditional Turing machine model helps us to translate the bounds obtained for circuits into bounds for the Turing machine model which is otherwise hard to analyze. In this thesis, we study the power of certain kinds of uniform constant depth circuits and provide upper and lower bounds. When we talk about Turing machines, the most important resources are time and space. The most important resources in case of Boolean circuits are size and depth. Circuits that have constant depth and polynomial size have been studied intensely in the last decade or so. The class AC0, consisting of languages accepted by constant depth, polynomial size circuits that have NOT gated, and unbounded fan-in AND and OR gates are very well understood and good lower bounds are known for it. On the other hand, the class ACC, that consists of languages accepted by constant depth, polynomial size circuits that have NOT gated, and unbounded fan-in AND, OR and MODm gates, for various moduli m, is not well understood at all. It is consistent with our knowledge that an ACC circuit family can compute the Satisfiability problem.
In this thesis, we prove that we need exponential size to compute the Permanent function using uniform circuit families that have constant depth and consist of NOT gates, and unbounded fan-in AND, OR and MOD gates. We also show that there are languages in PP and C=P that cannot be recognized by uniform ACC type circuits of subexponential size. We also study the question of finding a strong separation between NP and AC0. We show that non-relativizing proof techniques result from any answer to the question Does NP contain sets that are immune to AC0 ?." It is also shown that PPP contains sets that are immune to ACC and hence to AC0. Neil Jones introduced logspace reductions as a tool for studying the relative complexity of problems in P. He also introduced a restricted version of logspace reducibility, called logspace bounded rudimentary reductions to study small complexity classes like Dspace(log n). We show that these logspace bounded rudimentary reductions characterize uniform AC0.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).