Proving lower bounds on the amount of resources needed to compute specific functions is one of the most active branches of theoretical computer science. Significant progress has been made recently in proving lower bounds in two restricted models of Boolean circuits. One is the model of small depth circuits, and in this book Johan Torkel Hastad has developed very powerful techniques for proving exponential lower bounds on the size of small depth circuits' computing functions. The techniques described in Computational Limitations (...) for Small Depth Circuits can be used to demonstrate almost optimal lower bounds on the size of small depth circuits computing several different functions, such as parity and majority. The main tool used in the proof of the lower bounds is a lemma, stating that any AND of small fanout OR gates can be converted into an OR of small fanout AND gates with high probability when random values are substituted for the variables. Hastad also applies this tool to relativized complexity, and discusses in great detail the computation of parity and majority in small depth circuits. Contents: Introduction. Small Depth Circuits. Outline of Lower Bound Proofs. Main Lemma. Lower Bounds for Small Depth Circuits. Functions Requiring Depth k to Have Small Circuits. Applications to Relativized Complexity. How Well Can We Compute Parity in Small Depth? Is Majority Harder than Parity? Conclusions. John Hastad is a postdoctoral fellow in the Department of Mathematics at MIT Computational Limitations of Small Depth Circuits is a winner of the 1986 ACM Doctoral Dissertation Award. (shrink)

People have always been interested in numbers, in particular the natural numbers. Of course, we all have an intuitive notion of what these numbers are. In the late 19th century mathematicians, such as Grassmann, Frege and Dedekind, gave definitions for these familiar objects. Since then the development of axiomatic schemes for arithmetic have played a fundamental role in a logical understanding of mathematics. There has been a need for some time for a monograph on the metamathematics of first-order arithmetic. The (...) aim of the book by Hajek and Pudlak is to cover some of the most important results in the study of a first order theory of the natural numbers, called Peano arithmetic and its fragments (subtheories). The field is quite active, but only a small part of the results has been covered in monographs. This book is divided into three parts. In Part A, the authors develop parts of mathematics and logic in various fragments. Part B is devoted to incompleteness. Part C studies systems that have the induction schema restricted to bounded formulas (Bounded Arithmetic). One highlight of this section is the relation of provability to computational complexity. The study of formal systems for arithmetic is a prerequisite for understanding results such as Gödel's theorems. This book is intended for those who want to learn more about such systems and who want to follow current research in the field. The book contains a bibliography of approximately 1000 items. (shrink)

We define theories of bounded arithmetic, whose definable functions and relations are exactly those in certain complexity classes. Based on a recursion-theoretic characterization of NC in Clote , the first-order theory TNC, whose principal axiom scheme is a form of short induction on notation for nondeterministic polynomial-time computable relations, has the property that those functions having nondeterministic polynomial-time graph Θ such that TNC x y Θ are exactly the functions in NC, computable on a parallel random-access machine in polylogarithmic parallel (...) time with a polynomial number of processors.0 We then define three theories of weak second-order arithmetic which respectively characterize relations in the classes of alternating logarithmic time, logspace and nondeterministic logspace. (shrink)

Allen, B., Arithmetizing Uniform NC, Annals of Pure and Applied Logic 53 1–50. We give a characterization of the complexity class Uniform NC as an algebra of functions on the natural numbers which is the closure of several basic functions under composition and a schema of recursion. We then define a fragment of bounded arithmetic, and, using our characterization of Uniform NC, show that this fragment is capable of proving the totality of all of the functions in Uniform NC. Lastly, (...) in the spirit of Buss, we show that any function which is definable by a ∑b1-formula in our theory is a function which is in Uniform NC. (shrink)