Wegener I. The Complexity of Boolean Functions

формат pdf
размер 1.88 МБ
добавлен 11 мая 2011 г.

Wegener I. The Complexity of Boolean Functions. (Wiley-Teubner series in computer science).
John Wiley & Sons Ltd, and B. G. Teubner, Stuttgart, 1987.
Различные аспекты теории сложности: булевы функции, схемы, формулы, программы итд.
Булевы функции и схемы.
Минимизация булевых функций.
Разработка эффективных схем для некоторых важных функций.
Асимптотики и универсальные схемы.
Нижние границы сложности схем.
Монотонные схемы.
Связь между сложностью схем, сложностью формул и их глубиной.
Сложность формул.
Схемы vs. машин Тьюринга.
Иерархии, массовые произведения и редукции.
Схемы ограниченной глубины.
Синхронные, планарные и вероятностные схемы.
PRAM’ы и WRAM’ы.
Ветвящиеся программы.

Похожие разделы

Смотрите также

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...

Crama Y., Hammer P.L. Boolean Functions. Theory, Algorithms, and Applications

формат pdf
размер 4.54 МБ
добавлен 25 сентября 2011 г.

Издательство Cambridge University Press, 2011, -711 pp. Boolean functions, meaning {0,1}-valued functions of a finite number of {0,1}- valued variables, are among the most fundamental objects investigated in pure and applied mathematics. Their importance can be explained by several interacting factors. It is reasonable to argue that a multivariate function f :A1?A2?. . .?An? A is interesting only if each of the sets A1,A2, . . . ,An, and A cont...

Givant S., Halmos P. Introduction to Boolean Algebras

формат pdf
размер 3.54 МБ
добавлен 24 октября 2011 г.

Издательство Springer, 2009, -588 pp. Серия Undergraduate Texts in Mathematics The theory of Boolean algebras was created in 1847 by the English mathematician George Boole. He conceived it as a calculus (or arithmetic) suitable for a mathematical analysis of logic. The form of his calculus was rather different from the modern version, which came into being during the period 1864–1895 through the contributions of William Stanley Jevons, Augustus...

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...

Lam W.K.C., Brayton B.K. Timed Boolean Functions. A Unified Formalism for Exact Timing Analysis

формат djvu
размер 3.64 МБ
добавлен 28 октября 2011 г.

Издательство Kluwer, 1994, -297 pp. Timing research in high performance VLSI systems has advanced at a steady pace over the last few years, while tools, especially theoretical mechanisms, lag behind. Much present timing research relies heavily on timing diagrams, which, although intuitive, are inadequate for analysis of large designs with many parameters. Further, timing diagrams offer only approximations, not exact solutions, to many timing pro...

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...

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...

Steinbach B., Posthoff C. Logic Functions and Equations: Examples and Exercises

формат pdf
размер 2.84 МБ
добавлен 28 декабря 2010 г.

Springer, 2009. - 234 Pages. The field of binary Logics has two main areas of application, the Digital Design of Circuits (related to Electrical Engineering) and Propositional Logics (related to Mathematics, Artificial Intelligence, Complexity etc. ). In both cases it is quite possible to teach the theoretical foundations and to do some exercises, but in both cases the examples that can be done in class and by hand are far away from examples tha...