Computational complexity of Boolean functions

摘要: Boolean functions are among the fundamental objects of discrete mathematics, especially in those its subdisciplines which fall under mathematical logic and cybernetics. The language is convenient for describing operation many systems such as contact networks, circuits, branching programs, some others. An important parameter this kind their complexity. This characteristic has been actively investigated starting from Shannon's works. There a large body scientific literature presenting results. purpose survey to give an account main results over last sixty years related complexity computation (realization) by circuits without branching. Bibliography: 165 titles.