EN|RU

Том 4, серия 1, номер 3, 1997 г., Стр. 69-80

УДК 519.7
А. В. Чашкин
Локальная сложность булевых функций

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

Чашкин А. В. 1
1. МГУ, мех.-мат. факультет
Воробьевы горы, 119899 Москва, Россия

Статья поступила 28 апреля 1997 г.

 © Институт математики им. С. Л. Соболева, 2015