Локальная сложность булевых функций

Вводятся классы локально сложных и локально простых функций. Доказывается инвариантность этих классов относительно полиномиально эквивалентных мер сложности. Рассматривается связь между доказательством принадлежности функции классу локально сложных функций и доказательством нижних оценок сложности для схем из функциональных элементов, контактных схем, формул и параллельно-последовательных контактных схем.
Библиогр. 6