Дискретная математика
Математика
  • формат pdf
  • размер 7.78 МБ
  • добавлен 31 января 2012 г.
Vollmer H. Introduction to Circuit Complexity. A Uniform Approach
Издательство Springer, 1995, -287 pp.

This introductory textbook presents an algorithmic and computability based approach to circuit complexity. Intertwined with the consideration of practical examples and the design of efficient circuits for these, a lot of care is spent on the formal development of the computation model of uniform circuit families and the motivation of the complexity classes defined in this model.
Boolean circuits gain much of their attractiveness from the fact that nontrivial lower bounds for the complexity of particular practical problems in this model are known. However, I feel that circuit complexity should not be reduced to the theory of lower bounds. In the past few years, the study of complexity classes defined by Boolean circuits, as well as their properties and how they relate to other computational devices, has become more and more important. Best known are probably the cl asses that form the NC hierarchy, which was defined to capture the notion of problems that have very fast parallel algorithms using a feasible amount of hardware. This study is thus motivated from an algorithmic point of view, and therefore an important issue is the so-called uniformity of circuits, because only a uniform circuit family can be regarded as an implementation of an algorithm.
This book p resents some classical as well as some recent ' lower bound proofs; however, I restrict myself to a small and subjective selection of important examples. The reader who is interested in exploring this t opic further is directed to other textbooks (an extensive list of pointers to excellent literature is given in the Bibliographic Remarks of this book). Here, instead, the theory of circuit complexity classes, mostly connected with the NC hierarchy mentioned above, is developed thoroughly.
It is difficult, in times of such rapid developments in a field as we witness today in circuit complexity, to write a textbook which is not already out of date when it is published. Therefore the material presented here is chosen from a basic core of fundamental results which underlies most current research in circuit complexity and hopefully will still be important in the future. Of course a textbook of this size cannot even touch all important and interesting developments in circuit complexity. However, I have increase d the number of topics and results by covering some of them in the exercises, and introducing others in the Bibliographic Remarks sections.
The first three chapters can be used for a one-semester introduction to circuit complexity on the advanced undergraduate or first-year graduate level. (For readers familiar with the German university system, I have used Chaps. 1-3 for a Hauptstudiumsvorlesung Schaltkreiskomplexitiit for students with a moderate background in theoretical computer science.) The second half of the book, suited for an ongoing course or an advanced seminar, requires more experience from the reader, but is certainly still accessible to first-year graduate students.
The reader is expected to possess some knowledge and experience about formal languages and complexity of deterministic and nondeterministic Turing machines, as usually gained in a one-semester introduction to foundations of computing (refer, e.g., to [HU79]) . Besides this only basic mathematics is required (however, experience in a standard programming language will be helpful) . An except ion from this is Chap.
6. While I have tried to keep the exposition self-contained by introducing all necessary concepts, a full comprehension of most of the results presented in this final chapter will probably only be possible for a student familiar with the basic notions and results from complexity theory.
A few notes about how to use this book: Generally, each chapter presupposes the material of the preceding chapters. It is suggested that the reader quickly browse the Appendix "Mathematical Preliminaries" (p. 233) before starting with the main text, and then later study them in more detail as necessary. Each chapter ends with a number of exercises. Most exercises can be answered immediately if the material of the text has been understood. Starred exercises require some afterthought and more time. Double-starred exercises present quite difficult or lengthy problems. For most starred and all double- starred exercises, a pointer to the literature where a solution can be found is given.
Current information on this book may be found on the Web at the following location: http://www-info4.informatik.uni-wuerzburg.de/CC/ If you find errors in the book, please report them using the above URL; or send an e-mail to vollmer@ informatik.uni-wuerzburg.de.
Complexity Measures and Reductions.
Relations to Other Computation Models.
Lower Bounds.
The NC Hierarchy.
Arithmetic Circuits.
Polynomial Time and Beyond.
Похожие разделы
Смотрите также

Albertson M.O., Hutchinson J.P. Discrete Mathematics with Algorithms

  • формат pdf
  • размер 5.85 МБ
  • добавлен 23 октября 2011 г.
Издательство John Wiley, 2002, -552 pp. Here is a first-year course in discrete mathematics, requiring no calculus or computer programming experience, for students on computer science and mathematics courses. The approach stresses finding efficient algorithms, rather than existential results. It provides an introduction to constructing proofs (especially by induction), and an introduction to algorithmic problem solving. All algorithms are presen...

Buss S. Circuit Complexity and Computational Complexity

Статья
  • формат pdf
  • размер 573.37 КБ
  • добавлен 24 октября 2011 г.
University of California, 1992, -154 pp. These lecture notes were written for a topics course in the Mathematics Department at the University of California, San Diego during the winter and spring quarters of 1992. Introduction to circuit complexity. Theorems of Shannon and Lupanov giving upper and lower bounds of circuit complexity of almost all Boolean functions. Spira's theorem relating depth and formula size. Khrapchenko's lower bound on formu...

Chikalov I. Average Time Complexity of Decision Trees

  • формат pdf
  • размер 975.04 КБ
  • добавлен 09 ноября 2011 г.
Издательство Springer, 2011, -114 pp. The monograph is devoted to theoretical and experimental study of decision trees with a focus on minimizing the average time complexity. The study resulted in upper and lower bounds on the minimum average time complexity of decision trees for identification problems. Previously known bounds from information theory are extended to the case of identification problem with an arbitrary set of attributes. Some ex...

Creignou N., Kolaitis P.G., Vollmer H. (eds.) Complexity of Constraints. An Overview of Current Research Themes

  • формат pdf
  • размер 2.41 МБ
  • добавлен 17 декабря 2011 г.
Издательство Springer, 2008, -326 pp. In October 2006, the editors of this volume organized a Dagstuhl Seminar on Complexity of Constraints at the Schloss Dagstuhl Leibniz Center for Informatics inWadern, Germany. This event consisted of both invited and contributed talks by some of the approximately 40 participants, as well as problem sessions and informal discussions. After the conclusion of the seminar, the organizers invited a number of spea...

Jukna S. Boolean Function Complexity. Advances and Frontiers

  • формат pdf
  • размер 2.98 МБ
  • добавлен 24 октября 2011 г.
Издательство Springer, 2011, -633 pp. Boolean circuit complexity is the combinatorics of computer science and involves many intriguing problems that are easy to state and explain, even for the layman. This book is a comprehensive description of basic lower bound arguments, covering many of the gems of this complexity Waterloo that have been discovered over the past several decades, right up to results from the last year or two. Many open problems...

Lamagna E.A. The Complexity of Monotone Functions

Дисертация
  • формат pdf
  • размер 1.24 МБ
  • добавлен 15 декабря 2011 г.
Диссертация, Brown University, 1975, -110 pp. An important open question in the field of computational complexity is the development of nontrivial lower bounds on the number of logical operations required to compute switching functions. Two important measures of functional complexity are combinational complexity, corresponding to the minimal number of operations in any computational chain (straight-line algorithm or feedback-free network) for th...

Novak L., Gibbons A. Hybrid Graph Theory and Network Analysis

  • формат djvu
  • размер 1.2 МБ
  • добавлен 02 февраля 2012 г.
Издательство Cambridge University Press, 1999, -187 pp. This research monograph is concerned with two dual structures in graphs. These structures, one based on the concept of a circuit and the other on the concept of a cutset are strongly interdependent and constitute a hybrid structure called a graphoid. This approach to graph theory dealing with graphoidal structures we call hybrid graph theory. A large proportion of our material is either new...

Papadimitriou C.M. Computational Complexity

  • формат djvu
  • размер 4.5 МБ
  • добавлен 28 октября 2011 г.
Издательство Addison-Wesley, 1994, -540 pp. This book is an introduction to the theory of computational complexity at a level appropriate for a beginning graduate or advanced undergraduate course. Computational complexity is the area of computer science that contemplates the reasons why some problems are so hard to solve by computers. This field, virtually non-existent only 20 years ago, has expanded tremendously and now comprises a major part of...

Paterson M.S. (ed.) Boolean Function Complexity

  • формат djvu
  • размер 1.16 МБ
  • добавлен 28 октября 2011 г.
Издательство Cambridge University Press, 1992, -211 pp. Complexity theory attempts to understand and measure the intrinsic difficulty of computational tasks. The study of Boolean Function Complexity reaches for the combinatorial origins of these difficulties. The field was pioneered in the 1950's by Shannon, Lupanov and others, and has developed now into one of the most vigorous and challenging areas of theoretical computer science. In July 1990...

Savage J.E. Models of Computation. Exploring the Power of Computing

  • формат pdf
  • размер 4.2 МБ
  • добавлен 28 октября 2011 г.
Издательство Addison-Wesley, 1998, -699 pp. Theoretical computer science treats any computational subject for which a good model can be created. Research on formal models of computation was initiated in the 1930s and 1940s by Turing, Post, Kleene, Church, and others. In the 1950s and 1960s programming languages, language translators, and operating systems were under development and therefore became both the subject and basis for a great deal of...