Том 4, серия 1, номер 3, 1997 г., Стр. 69-80
УДК 519.7
А. В. Чашкин
Локальная сложность булевых функций
Аннотация:
Вводятся классы локально сложных и локально простых функций. Доказывается инвариантность этих классов относительно полиномиально эквивалентных мер сложности. Рассматривается связь между доказательством принадлежности функции классу локально сложных функций и доказательством нижних оценок сложности для схем из функциональных элементов, контактных схем, формул и параллельно-последовательных контактных схем.
Библиогр. 6.
Чашкин А. В. 1
1. МГУ, мех.-мат. факультет
Воробьевы горы, 119899 Москва, Россия
Статья поступила 28 апреля 1997 г.
|